結果

問題 No.3118 Increment or Multiply
ユーザー keigo kuwata
提出日時 2025-04-23 08:40:26
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 584 ms / 2,000 ms
コード長 1,361 bytes
コンパイル時間 353 ms
コンパイル使用メモリ 12,288 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2025-04-23 08:40:36
合計ジャッジ時間 9,232 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353
INV2 = (MOD + 1) // 2

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N, A = map(int, input().split())
    # A=1 の特別扱い
    if A == 1:
        # N*(N-1)//2 % MOD
        n_mod = N % MOD
        ans = n_mod * ((n_mod - 1) % MOD) % MOD * INV2 % MOD
        print(ans)
        continue

    # (1) base-A 表記で N を分解しつつ L_j = floor(N/A^j), d_j = N mod A
    L = []  # L[j] = N // A^j
    d = []  # d[j] = (N // A^j) % A
    cur = N
    while cur > 0:
        L.append(cur)
        d.append(cur % A)
        cur //= A
    m_max = len(L) - 1

    # (2) C_j = sum_{i=0..j-1} d[i]
    C = [0] * (m_max + 1)
    for j in range(1, m_max + 1):
        C[j] = C[j-1] + d[j-1]

    # (3) V_j = L_j + j + C_j, U_j = min(V_0..V_j)
    V = [0] * (m_max + 1)
    for j in range(m_max + 1):
        V[j] = L[j] + j + C[j]
    U = [0] * (m_max + 1)
    U[0] = V[0]
    for j in range(1, m_max + 1):
        U[j] = min(U[j-1], V[j])

    # (4) 区間ごとの和 sum W(K)
    #    L_{m_max+1} = 0 とみなす
    L.append(0)
    sumW = 0
    for j in range(m_max + 1):
        cnt = (L[j] - L[j+1]) % MOD
        sumW = (sumW + cnt * (U[j] % MOD)) % MOD

    # (5) 最終的な答え
    n_mod = N % MOD
    sumn = n_mod * ((n_mod + 1) % MOD) % MOD * INV2 % MOD
    ans = (sumW - sumn) % MOD
    print(ans)
0