結果

問題 No.3607 Sum of Powers of GCDs
コンテスト
ユーザー 👑 loop0919
提出日時 2026-04-12 01:38:41
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,295 ms / 2,500 ms
+ 462µs
コード長 1,460 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 243 ms
コンパイル使用メモリ 95,980 KB
実行使用メモリ 266,616 KB
最終ジャッジ日時 2026-07-31 20:50:14
合計ジャッジ時間 12,189 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

LIM_M = 10**6
LIM_K = 10
MOD = 998244353

acc_jordan: list[list[int]]

def prev():
    global acc_jordan

    # spf[i] := i の最小素因数
    spf = [0] * (LIM_M + 1)
    primes = []
    for i in range(2, LIM_M + 1):
        if spf[i] == 0:
            spf[i] = i
            primes.append(i)
        for p in primes:
            v = i * p
            if v > LIM_M or p > spf[i]:
                break
            spf[v] = p

    # jordan[k][n] := Jordan のトーシェント関数 J_k(n)
    jordan = [[1] * (LIM_M + 1) for _ in range(LIM_K + 1)]
    for k in range(1, LIM_K + 1):
        for n in range(2, LIM_M + 1):
            m = n // spf[n]
            if m % spf[n] == 0:
                jordan[k][n] = jordan[k][m] * pow(spf[n], k, MOD) % MOD
            else:
                jordan[k][n] = jordan[k][m] * (pow(spf[n], k, MOD) - 1) % MOD

    # Jordan のトーシェント関数の累積和
    acc_jordan = [[0] * (LIM_M + 2) for k in range(LIM_K + 1)]
    for k in range(1, LIM_K + 1):
        for n in range(LIM_M + 1):
            acc_jordan[k][n + 1] = (acc_jordan[k][n] + jordan[k][n]) % MOD

def solve():
    N, M, K = [int(s) for s in input().split()]
    ans = 0

    l = 1
    while l <= M:
        q = M // l
        r = M // q
        sum_j = (acc_jordan[K][r + 1] - acc_jordan[K][l]) % MOD
        ans = (ans + sum_j * pow(q, N, MOD)) % MOD
        l = r + 1

    print(ans)

T = int(input())
prev()
for _ in range(T):
    solve()
0