結果
問題 | 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 1if p==998244353:return 3if p==10**9+7:return 5if p==163577857:return 23if p==167772161:return 3if p==469762049:return 3fac=[]q=2v=p-1while v>=q*q:e=0while v%q==0:e+=1v//=qif e>0:fac.append(q)q+=1if v>1:fac.append(v)g=2while g<p:if pow(g,p-1,p)!=1:return Noneflag=Truefor q in fac:if pow(g,(p-1)//q,p)==1:flag=Falsebreakif flag:return gg+=1#================================================T=int(input())for _ in range(T):v,x=map(int,input().split())p=v*x+1g=Primitive_Root(p)r=pow(g,v,p)A=[]a=1for __ in range(x):A.append(a)a=(a*r)%pA.sort()print(*A)