結果
問題 |
No.1164 GCD Products hard
|
ユーザー |
![]() |
提出日時 | 2025-04-15 21:52:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,076 ms / 2,500 ms |
コード長 | 999 bytes |
コンパイル時間 | 553 ms |
コンパイル使用メモリ | 82,464 KB |
実行使用メモリ | 187,080 KB |
最終ジャッジ日時 | 2025-04-15 21:54:11 |
合計ジャッジ時間 | 18,091 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 |
ソースコード
def main(): import sys A, B, N = map(int, sys.stdin.readline().split()) MOD = 10**9 + 7 MOD_MINUS_1 = MOD - 1 # Sieve of Eratosthenes to find all primes up to B if B < 2: print(1) return is_prime = [True] * (B + 1) is_prime[0] = is_prime[1] = False for i in range(2, int(B**0.5) + 1): if is_prime[i]: for j in range(i * i, B + 1, i): is_prime[j] = False primes = [i for i, prime in enumerate(is_prime) if prime] result = 1 for p in primes: sum_e = 0 current_power = p while current_power <= B: m = current_power cnt = B // m - (A - 1) // m if cnt <= 0: break term = pow(cnt, N, MOD_MINUS_1) sum_e = (sum_e + term) % MOD_MINUS_1 current_power *= p if sum_e != 0: result = (result * pow(p, sum_e, MOD)) % MOD print(result) if __name__ == "__main__": main()