結果

問題 No.1164 GCD Products hard
ユーザー LyricalMaestro
提出日時 2025-10-28 02:19:12
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 645 bytes
コンパイル時間 348 ms
コンパイル使用メモリ 82,576 KB
実行使用メモリ 198,808 KB
最終ジャッジ日時 2025-10-28 02:19:20
合計ジャッジ時間 8,123 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/573

MOD = 10 ** 9 + 7

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

    dp = [0] * (B + 1)
    cache = [-1] * (B + 1)

    for b in reversed(range(1, B + 1)):
        x = B // b - (A - 1) // b
        if cache[x] == -1:
            cache[x] = pow(x, N, MOD - 1)
        y = cache[x]

        z = 2 * b
        while z <= B:
            y -= dp[z]
            y %= (MOD - 1)
            z += b
        dp[b] = y

    answer = 1
    for b in range(1, B + 1):
        x = pow(b, dp[b], MOD)
        answer *= x
        answer %= MOD
    print(answer)
        






if __name__ == '__main__':
    main()
0