結果

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

ソースコード

diff # 

import sys

def solve_case(N, A, mod, inv2):
    # Case A = 1: f(K) = N - K, sum = N*(N-1)//2
    if A == 1:
        n_mod = N % mod
        return n_mod * ((n_mod - 1 + mod) % mod) % mod * inv2 % mod

    # Build sequence N_i: N_0 = N, N_{i+1} = floor(N_i / A), until N_i = 0
    Ni = [N]
    while Ni[-1] > 0:
        Ni.append(Ni[-1] // A)
    # Precompute prefix sums of remainders R[i] = sum_{k=0..i-1} (Ni[k] mod A)
    M = len(Ni) - 1  # Ni[M] = 0
    R = [0] * (M + 1)
    for i in range(1, M + 1):
        R[i] = R[i-1] + (Ni[i-1] % A)
    R_mod = [r % mod for r in R]

    result = 0
    # Helper to compute s(x) = x*(x+1)//2 mod
    def sum_upto(x):
        x_mod = x % mod
        return x_mod * ((x + 1) % mod) % mod * inv2 % mod

    for i in range(M):
        n_i = Ni[i]
        n_next = Ni[i+1]
        length = n_i - n_next  # number of K in (N_{i+1}, N_i]
        # term1 = length * (R[i] + i + N_i)
        term1 = length % mod * ((R_mod[i] + i) % mod + (n_i % mod)) % mod
        # term2 = sum_{K=n_next+1..n_i} K = s(n_i) - s(n_next)
        term2 = (sum_upto(n_i) - sum_upto(n_next)) % mod
        result = (result + term1 - term2) % mod
    return result


def main():
    input_data = sys.stdin.read().split()
    t = int(input_data[0])
    mod = 998244353
    inv2 = pow(2, mod-2, mod)
    out = []
    idx = 1
    for _ in range(t):
        N = int(input_data[idx]); A = int(input_data[idx+1])
        idx += 2
        out.append(str(solve_case(N, A, mod, inv2)))
    sys.stdout.write("\n".join(out))

if __name__ == '__main__':
    main()
0