結果
問題 | No.1728 [Cherry 3rd Tune] Bullet |
ユーザー | tamato |
提出日時 | 2021-10-29 23:35:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 102 ms / 2,000 ms |
コード長 | 1,338 bytes |
コンパイル時間 | 178 ms |
コンパイル使用メモリ | 82,816 KB |
実行使用メモリ | 76,840 KB |
最終ジャッジ日時 | 2024-04-16 15:59:59 |
合計ジャッジ時間 | 2,552 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 40 ms
52,352 KB |
testcase_01 | AC | 43 ms
52,224 KB |
testcase_02 | AC | 42 ms
52,480 KB |
testcase_03 | AC | 46 ms
52,736 KB |
testcase_04 | AC | 41 ms
52,480 KB |
testcase_05 | AC | 46 ms
58,368 KB |
testcase_06 | AC | 48 ms
58,880 KB |
testcase_07 | AC | 47 ms
58,496 KB |
testcase_08 | AC | 59 ms
59,904 KB |
testcase_09 | AC | 59 ms
58,624 KB |
testcase_10 | AC | 69 ms
60,672 KB |
testcase_11 | AC | 57 ms
60,032 KB |
testcase_12 | AC | 60 ms
60,544 KB |
testcase_13 | AC | 63 ms
60,032 KB |
testcase_14 | AC | 60 ms
59,136 KB |
testcase_15 | AC | 66 ms
59,392 KB |
testcase_16 | AC | 62 ms
60,288 KB |
testcase_17 | AC | 60 ms
58,624 KB |
testcase_18 | AC | 60 ms
59,264 KB |
testcase_19 | AC | 59 ms
60,032 KB |
testcase_20 | AC | 57 ms
59,056 KB |
testcase_21 | AC | 63 ms
59,264 KB |
testcase_22 | AC | 63 ms
59,604 KB |
testcase_23 | AC | 102 ms
76,672 KB |
testcase_24 | AC | 94 ms
76,840 KB |
testcase_25 | AC | 60 ms
58,624 KB |
testcase_26 | AC | 56 ms
60,544 KB |
ソースコード
mod = 1000000007 eps = 10**-9 def main(): import sys from math import gcd input = sys.stdin.readline def PrimeDecomposition(N): ret = {} n = int(N ** 0.5) for d in range(2, n + 1): while N % d == 0: if d not in ret: ret[d] = 1 else: ret[d] += 1 N //= d if N == 1: break if N != 1: ret[N] = 1 return ret def euler_phi(N, P): P = PrimeDecomposition(N) ret = N for p in P: ret = ret * (p - 1) // p return ret T = int(input()) for _ in range(T): N, C = map(int, input().split()) P = PrimeDecomposition(N) div = [] for d in range(1, N+1): if d * d > N: break if N%d == 0: div.append(d) div.append(N // d) if div[-1] ** 2 == N: div.pop() #ans = pow(C, 2*N, mod) ans = 0 for d in div: x = pow(C ** 2, d, mod) ans = (ans + (x * euler_phi(N // d, P))%mod)%mod ans = (ans + (pow(C, N, mod) * N)%mod)%mod ans = (ans * pow(2*N, mod-2, mod))%mod print(ans) if __name__ == '__main__': main()