結果

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

ソースコード

diff # 

MOD = 10**9 + 7
MOD_PHI = MOD - 1

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

max_d = B
g = [0] * (max_d + 1)
count = [0] * (max_d + 1)

for d in range(1, max_d + 1):
    lower = (A - 1) // d
    upper = B // d
    cnt = upper - lower
    count[d] = pow(cnt, N, MOD_PHI)

# Process in reverse order to use inclusion-exclusion principle
for d in range(max_d, 0, -1):
    start = d * 2
    sum_g = 0
    if start <= max_d:
        # Sum all g for multiples of d beyond d itself
        sum_g = sum(g[start::d]) % MOD_PHI
    # Calculate g[d] using inclusion-exclusion
    g[d] = (count[d] - sum_g) % MOD_PHI

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

print(result)
0