結果

問題 No.3118 Increment or Multiply
コンテスト
ユーザー keigo kuwata
提出日時 2025-04-24 14:34:13
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 246 ms / 2,000 ms
コード長 873 bytes
コンパイル時間 461 ms
コンパイル使用メモリ 12,160 KB
実行使用メモリ 10,368 KB
最終ジャッジ日時 2025-04-24 14:34:19
合計ジャッジ時間 6,105 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def solve_case(N, A):
    # A=1 の特別扱い
    if A == 1:
        # sum_{K=1..N}(N-K) = N(N-1)/2
        return (N % MOD) * ((N - 1) % MOD) * pow(2, MOD-2, MOD) % MOD

    res = 0
    while N > 0:
        M1 = N // A        # floor(N/A)
        d0 = N - A * M1    # N mod A
        d = N - M1         # 要素数

        # 1) 引き算だけで到達する区間のコスト ∑(N-K)
        #    = d*(d-1)/2
        res = (res + d * (d - 1) // 2) % MOD

        # 2) それ以外 (K≤M1) は d0 回の -1 と 1 回の ÷A が共通
        #    = M1 * (d0 + 1)
        res = (res + M1 * (d0 + 1)) % MOD

        # 再帰的に N ← M1 に縮小
        N = M1

    return res

# 入力読み込み・出力
import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N, A = map(int, input().split())
    print(solve_case(N, A))
0