結果

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

ソースコード

diff # 

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

MOD = 10 ** 9 + 7

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

    # 素数列挙
    primes = []
    is_primes = [True] * (B + 1)
    for p in range(2, B + 1):
        if not is_primes[p]:
            continue

        x = 2 * p
        primes.append(p)
        while x <= B:
            is_primes[x] = False
            x += p

    pow_n = [0] * ((B // 2) + 1)
    for b in range(1, (B // 2) + 1):
        pow_n[b] = pow(b, N, MOD - 1)
        
    answer = 1
    for p in primes:
        p1 = p
        z = 0
        while p1 <= B:
            x = B // p1 - (A - 1) // p1
            if x > 0:
                z += pow_n[x]
                z %= (MOD - 1)
            p1 *= p
        answer *= pow(p, z, MOD)
        answer %= MOD
    print(answer)

        





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