結果

問題 No.3118 Increment or Multiply
ユーザー miya145592
提出日時 2025-04-21 02:23:40
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 171 ms / 2,000 ms
コード長 643 bytes
コンパイル時間 454 ms
コンパイル使用メモリ 82,660 KB
実行使用メモリ 78,676 KB
最終ジャッジ日時 2025-04-21 02:23:46
合計ジャッジ時間 5,819 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
MOD = 998244353
T = int(input())
NA = [list(map(int, input().split())) for _ in range(T)]
for n, a in NA:
    if a==1:
        ans = (n-1)*n//2
        print(ans%MOD)
    else:
        y = n
        ans = 0
        m = []
        first = 1
        cnt = 0
        while y>0:
            x = y//a
            if first:
                ans += (n-(x+1))*(n-x)//2
                first = 0
            else:
                ans += (y-(x+1))*(y-x)//2
                ans += (y-x)*cnt + sum(m)*(y-x)
            m.append(y%a)
            y = x
            cnt += 1
            #print(ans)
        print(ans%MOD)
0