結果

問題 No.3118 Increment or Multiply
コンテスト
ユーザー hir355
提出日時 2025-04-20 16:18:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 172 ms / 2,000 ms
コード長 534 bytes
コンパイル時間 517 ms
コンパイル使用メモリ 82,564 KB
実行使用メモリ 78,188 KB
最終ジャッジ日時 2025-04-20 16:18:55
合計ジャッジ時間 6,317 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353
t = int(input())
for _ in range(t):
    n, a = map(int, input().split())
    if a == 1:
        print((n * (n - 1) // 2) % MOD)
        continue
    t = []
    m = n
    while m > 0:
        t.append(m % a)
        m //= a
    t.reverse()
    m = len(t)
    s = sum(t)
    x = 0
    y = 0
    ans = 0
    for i in range(m):
        x *= a
        x += t[i]
        s -= t[i]
        k = x * (x - y) - (x * (x + 1) // 2 - y * (y + 1) // 2)
        ans += k + (s + m - i - 1) * (x - y)
        y = x
    print(ans % MOD)
0