結果
問題 |
No.1409 Simple Math in yukicoder
|
ユーザー |
👑 ![]() |
提出日時 | 2021-02-26 23:06:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 124 ms / 2,000 ms |
コード長 | 1,050 bytes |
コンパイル時間 | 287 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 77,676 KB |
最終ジャッジ日時 | 2024-10-02 15:58:31 |
合計ジャッジ時間 | 30,639 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 58 |
ソースコード
def Primitive_Root(p): """Z/pZ上の原始根を見つける p:素数 """ if p==2: return 1 if p==998244353: return 3 if p==10**9+7: return 5 if p==163577857: return 23 if p==167772161: return 3 if p==469762049: return 3 fac=[] q=2 v=p-1 while v>=q*q: e=0 while v%q==0: e+=1 v//=q if e>0: fac.append(q) q+=1 if v>1: fac.append(v) g=2 while g<p: if pow(g,p-1,p)!=1: return None flag=True for q in fac: if pow(g,(p-1)//q,p)==1: flag=False break if flag: return g g+=1 #================================================ T=int(input()) for _ in range(T): v,x=map(int,input().split()) p=v*x+1 g=Primitive_Root(p) r=pow(g,v,p) A=[] a=1 for __ in range(x): A.append(a) a=(a*r)%p A.sort() print(*A)