結果

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

ソースコード

diff # 

import sys
import threading

def main():
    import sys
    data = sys.stdin.read().split()
    it = iter(data)
    T = int(next(it))
    mod = 998244353
    out = []
    for _ in range(T):
        N = int(next(it))
        A = int(next(it))
        if A == 1:
            # f(K) = N - K, sum = N*(N-1)/2
            res = (N % mod) * ((N-1) % mod) % mod * pow(2, mod-2, mod) % mod
            out.append(str(res))
            continue
        # Precompute contributions
        total_N2 = (N % mod) * (N % mod) % mod
        sum_m = 0
        sum_PK = 0
        P = 1
        m = 0
        while P <= N:
            U = N // P
            # Next power
            # Watch for overflow: if P > N//A, then P*A > N
            if P > N // A:
                L = 0
            else:
                L = N // (P * A)
            count = U - L
            # sum of m contributions
            sum_m = (sum_m + m * (count % mod)) % mod
            # sum of P[m] * sum_{K=L+1..U} K
            # sumK = U*(U+1)//2 - L*(L+1)//2
            sumK = (U * (U + 1) // 2 - L * (L + 1) // 2) % mod
            sum_PK = (sum_PK + (P % mod) * sumK) % mod
            # next
            m += 1
            P *= A
        # result = N^2 + sum_m - sum_PK
        res = (total_N2 + sum_m - sum_PK) % mod
        out.append(str(res))
    sys.stdout.write("\n".join(out))

if __name__ == '__main__':
    main()
0