結果

問題 No.3118 Increment or Multiply
コンテスト
ユーザー nu
提出日時 2025-04-20 04:07:33
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,306 bytes
コンパイル時間 395 ms
コンパイル使用メモリ 12,288 KB
実行使用メモリ 195,064 KB
最終ジャッジ日時 2025-04-20 04:07:38
合計ジャッジ時間 4,478 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other AC * 5 TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
MOD = 998244353
def solve_case(N, A):
    visited = {}
    q = deque()
    q.append((N, 0))
    visited[N] = 0
    while q:
        cur, d = q.popleft()
        if cur > 1 and (cur - 1) not in visited:
            visited[cur - 1] = d + 1
            q.append((cur - 1, d + 1))
        if A > 1 and cur % A == 0:
            nxt = cur // A
            if nxt not in visited:
                visited[nxt] = d + 1
                q.append((nxt, d + 1))
        if len(visited) > 10**6:
            break
    total = 0
    for k, dist in visited.items():
        if k <= N:
            total += dist
            if total >= MOD:
                total -= MOD

    counted = sorted(k for k in visited if k <= N)
    counted_set = set(counted)
    def sum_arith(l, r):
        cnt = r - l + 1
        return ((cnt * ((N - l) + (N - r)) // 2) % MOD)
    last = 0
    for k in counted:
        if k - 1 >= last + 1:
            total += sum_arith(last + 1, k - 1)
            total %= MOD
        last = k
    if last < N:
        total += sum_arith(last + 1, N)
        total %= MOD
    return total
T = int(input())
for _ in range(T):
    N, A = map(int, input().split())
    if A == 1:
        ans = (N * (N - 1) // 2) % MOD
    else:
        ans = solve_case(N, A)
    print(ans)
0