結果
問題 |
No.1140 EXPotentiaLLL!
|
ユーザー |
👑 ![]() |
提出日時 | 2025-08-06 00:12:55 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 991 ms / 2,000 ms |
コード長 | 965 bytes |
コンパイル時間 | 416 ms |
コンパイル使用メモリ | 82,404 KB |
実行使用メモリ | 198,244 KB |
最終ジャッジ日時 | 2025-08-06 00:13:10 |
合計ジャッジ時間 | 14,320 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 12 |
ソースコード
""" https://yukicoder.me/problems/no/1140 """ from sys import stdin import math 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,divlis = Sieve(6000000) pset = set(plis) TT = int(stdin.readline()) ANS = [] for _ in range(TT): A,P = map(int,stdin.readline().split()) if P not in pset: ANS.append(-1) elif A % P == 0: ANS.append(0) else: ANS.append(1) print (*ANS,sep="\n")