結果

問題 No.3118 Increment or Multiply
ユーザー Naru820
提出日時 2025-06-02 09:53:16
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,088 bytes
コンパイル時間 386 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 599,968 KB
最終ジャッジ日時 2025-06-02 09:53:22
合計ジャッジ時間 5,658 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other AC * 5 MLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

import collections

MOD = 998244353

def solve():
    N, A = map(int, input().split())

    if A == 1:
        # A=1の場合、操作は+1のみなので f(K) = N - K
        # 総和は sum_{K=1 to N} (N-K) = sum_{j=0 to N-1} j = (N-1) * N / 2
        N_mod = N % MOD
        N_minus_1_mod = (N - 1) % MOD
        inv2 = pow(2, MOD - 2, MOD)
        ans = (N_mod * N_minus_1_mod) % MOD
        ans = (ans * inv2) % MOD
        print(ans)
        return

    # BFSで f(K) の総和を計算
    dist = {N: 0}
    q = collections.deque([N])
    total_sum = 0
    
    while q:
        u = q.popleft()
        c = dist[u]
        
        total_sum = (total_sum + c) % MOD
        
        # 操作1: -1
        v1 = u - 1
        if v1 > 0 and v1 not in dist:
            dist[v1] = c + 1
            q.append(v1)
            
        # 操作2: /A
        if u % A == 0:
            v2 = u // A
            if v2 > 0 and v2 not in dist:
                dist[v2] = c + 1
                q.append(v2)
                
    print(total_sum)


T = int(input())
for _ in range(T):
    solve()
0