結果
問題 |
No.3115 One Power One Kill
|
ユーザー |
👑 ![]() |
提出日時 | 2025-04-19 03:32:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 115 ms / 2,000 ms |
コード長 | 1,784 bytes |
コンパイル時間 | 371 ms |
コンパイル使用メモリ | 82,408 KB |
実行使用メモリ | 70,896 KB |
平均クエリ数 | 2.00 |
最終ジャッジ日時 | 2025-04-19 03:32:08 |
合計ジャッジ時間 | 3,817 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
""" https://yukicoder.me/problems/no/3115 まぁギャグだとは思うが Xが大きい素数の時、3では1が返ってくるのでそれを前提に考えよう まぁフェルマーの小定理 X^A mod B Bを素数にしておいて、A = B-1 にすると X' が1になってくれる場合が多い XがBの倍数の時 (xB)^(B-1) mod B は0になる?? gcd(X,Y) だけで、Xの倍数かチェックしないといけない うわ89はだめなのか 89*89はどうよ pow(B*B-1, B*B , mod) 17*29 = 493 ならどうか (17^t * x) ^ (17*29-1) mod (17*29) x^() の部分は 1 88^89 = 44^ --- 4で 1 or 0 になるのが理想 - Aは B-1 の倍数ならOK 3では、Kが Bの倍数かを判定したい """ """ def Sieve(n): #n以下の素数全列挙(O(nloglogn)) retは素数が入ってる。divlisはその数字の素因数が一つ入ってる ret = [] divlis = [-1] * (n+1) #何で割ったかのリスト(初期値は-1) flag = [True] * (n+1) flag[0] = False flag[1] = False ind = 2 while ind <= n: if flag[ind]: ret.append(ind) ind2 = ind ** 2 while ind2 <= n: flag[ind2] = False divlis[ind2] = ind ind2 += ind ind += 1 return ret,divlis plis,_ = Sieve(10**5) for B in plis: for A in range(B-1,10**5,B-1): if 100 <= B <= 10**5 and pow(A,B,10**9+7) % B == 0: print (A,B) """ A = 664 B = 167 Y = pow(A,B,10**9+7) print (A,B,flush=True) K = int(input()) if K % B == 0: print (0,flush=True) else: print (1,flush=True) """ print (88,89,flush=True) K = int(input()) if K % 89 == 0: print (0,flush=True) else: print (1,flush=True) cat = int(input()) """