結果

問題 No.3118 Increment or Multiply
コンテスト
ユーザー keigo kuwata
提出日時 2025-04-24 14:24:10
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 849 bytes
コンパイル時間 257 ms
コンパイル使用メモリ 12,032 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2025-04-24 14:24:19
合計ジャッジ時間 8,138 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 WA * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def solve_case(N, A):
    N_mod = N % MOD
    if A == 1:
        return N_mod * ((N - 1) % MOD) * pow(2, MOD-2, MOD) % MOD

    # 1) P[i]=A^i を列挙
    P = [1]
    while P[-1] <= N // A:
        P.append(P[-1] * A)
    m = len(P) - 1

    sum_p = 0
    sum_KA = 0
    for i, Pi in enumerate(P):
        Ri = N // Pi
        Li = 1 if i == m else (N // P[i+1]) + 1
        if Li > Ri:
            continue
        cnt = Ri - Li + 1
        # 区間和 (Li + Ri)*cnt/2 mod
        sK = (Li + Ri) * cnt // 2 % MOD

        sum_p = (sum_p + i % MOD * cnt) % MOD
        sum_KA = (sum_KA + (Pi % MOD) * sK) % MOD

    ans = (sum_p + N_mod * N_mod - sum_KA) % MOD
    return ans

# 入力処理
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
    N, A = map(int, input().split())
    print(solve_case(N, A))
0