結果
問題 |
No.1164 GCD Products hard
|
ユーザー |
![]() |
提出日時 | 2025-04-15 21:55:57 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,337 bytes |
コンパイル時間 | 333 ms |
コンパイル使用メモリ | 82,600 KB |
実行使用メモリ | 253,280 KB |
最終ジャッジ日時 | 2025-04-15 21:57:39 |
合計ジャッジ時間 | 7,849 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 2 |
other | TLE * 1 -- * 26 |
ソースコード
import sys MOD = 10**9 + 7 MOD_EXP = MOD - 1 def main(): A, B, N = map(int, sys.stdin.readline().split()) max_d = B f = [0] * (max_d + 1) # Precompute mobius function using sieve max_k = B mobius = [1] * (max_k + 1) is_prime = [True] * (max_k + 1) for p in range(2, max_k + 1): if is_prime[p]: for multiple in range(p, max_k + 1, p): is_prime[multiple] = False if multiple != p else is_prime[multiple] mobius[multiple] *= -1 p_square = p * p for multiple in range(p_square, max_k + 1, p_square): mobius[multiple] = 0 result = 1 for d in range(1, max_d + 1): current_sum = 0 k_max = B // d if k_max == 0: continue for k in range(1, k_max + 1): mu = mobius[k] if mu == 0: continue m = (B // (d * k)) - ((A - 1) // (d * k)) if m < 0: m = 0 term = mu * pow(m, N, MOD_EXP) current_sum += term if current_sum >= MOD_EXP or current_sum <= -MOD_EXP: current_sum %= MOD_EXP exponent = current_sum % MOD_EXP result = (result * pow(d, exponent, MOD)) % MOD print(result) if __name__ == "__main__": main()