結果

問題 No.1164 GCD Products hard
ユーザー lam6er
提出日時 2025-04-15 21:46:17
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 819 bytes
コンパイル時間 450 ms
コンパイル使用メモリ 82,508 KB
実行使用メモリ 126,276 KB
最終ジャッジ日時 2025-04-15 21:47:33
合計ジャッジ時間 7,980 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

A, B, N = map(int, input().split())

max_d = B
e = [0] * (max_d + 1)
total_e = 0

# Process d from B down to 2
for d in range(max_d, 1, -1):
    L = (A + d - 1) // d
    R = B // d
    m = R - L + 1
    if m < 1:
        e[d] = 0
        continue
    sum_e = 0
    k = 2
    while k * d <= max_d:
        sum_e = (sum_e + e[k * d]) % MOD
        k += 1
    current_e = (pow(m, N, MOD) - sum_e) % MOD
    e[d] = current_e
    total_e = (total_e + current_e) % MOD

# Process d=1
L = (A + 1 - 1) // 1
R = B // 1
m = R - L + 1  # m = B - A + 1
sum_e = total_e  # sum of e[2..B]
current_e = (pow(m, N, MOD) - sum_e) % MOD
e[1] = current_e

# Compute the final product
result = 1
for d in range(1, max_d + 1):
    if e[d] == 0:
        continue
    result = (result * pow(d, e[d], MOD)) % MOD

print(result)
0