結果

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

ソースコード

diff # 

MOD = 998244353

def modinv(x, m):
    return pow(x, m - 2, m)

def solve(N, A):
    if A == 1:
        # Sum of (N - K) for all K from 1 to N
        return (N * (N - 1) // 2) % MOD
    
    # Precompute powers of A up to N
    result = 0
    power_A = 1  # Start with A^0 which is 1
    m = 0
    
    while power_A <= N:
        # Current maximum value we can reach with A^m
        next_power = power_A * A
        if next_power > N:
            next_power = N + 1
        
        # Count how many K's fit this block
        # For each K in this block, we will calculate how many steps it takes to reach N
        count_in_block = N // power_A - N // next_power
        
        sum_of_Ks = (N * (N + 1) // 2 - (N // power_A) * (N // power_A + 1) // 2) % MOD
        
        result += (count_in_block * sum_of_Ks) % MOD
        result %= MOD
        
        m += 1
        power_A = next_power
        
    return result

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    T = int(data[0])
    idx = 1
    
    results = []
    
    for _ in range(T):
        N = int(data[idx])
        A = int(data[idx + 1])
        idx += 2
        result = solve(N, A)
        results.append(result)
    
    sys.stdout.write("\n".join(map(str, results)) + "\n")
    
if __name__ == "__main__":
    main()
0