結果
問題 | No.2191 一元二次式 mod 奇素数 |
ユーザー |
👑 ![]() |
提出日時 | 2023-01-13 21:44:49 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 44 ms / 2,000 ms |
コード長 | 6,285 bytes |
コンパイル時間 | 213 ms |
コンパイル使用メモリ | 82,060 KB |
実行使用メモリ | 55,424 KB |
最終ジャッジ日時 | 2024-12-24 16:56:48 |
合計ジャッジ時間 | 2,144 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
class Modulo():__slots__=("a","n")def __init__(self, a, n, mode=True):if mode:a%=nself.a=aself.n=ndef __str__(self):return "{} (mod {})".format(self.a, self.n)def __repr__(self):return self.__str__()#+,-def __pos__(self):return selfdef __neg__(self):if self.a:return Modulo(self.n-self.a, self.n,False)else:return Modulo(0, self.n, False)#等号,不等号def __eq__(self, other):if isinstance(other, Modulo):return (self.a==other.a) and (self.n==other.n)elif isinstance(other,int):return (self.a-other)%self.n==0def __neq__(self,other):return not(self==other)def __le__(self,other):a,p=self.a,self.nb,q=other.a,other.nreturn (a-b)%q==0 and p%q==0def __ge__(self,other):return other<=selfdef __lt__(self,other):return (self<=other) and (self!=other)def __gt__(self,other):return (self>=other) and (self!=other)def __contains__(self,val):return val%self.n==self.a#加法def __add__(self,other):if isinstance(other,Modulo):assert self.n==other.n, "異なる法同士の演算です."y=other.aelif isinstance(other,int):y=other%self.nb=self.a+yif self.n<=b:b-=self.nreturn Modulo(b,self.n, False)def __radd__(self,other):if isinstance(other,int):b=self.a+(other%self.n)if b>=self.n:b-=self.nreturn Modulo(b,self.n, False)def __iadd__(self,other):if isinstance(other,Modulo):assert self.n==other.n, "異なる法同士の演算です."y=other.aelif isinstance(other,int):y=other%self.nself.a+=yif self.a>=self.n:self.a-=self.nreturn self#減法def __sub__(self,other):if isinstance(other,Modulo):assert self.n==other.n, "異なる法同士の演算です."y=other.aelif isinstance(other,int):y=other%self.nb=self.a-yif b<0:b+=self.nreturn Modulo(b,self.n, False)def __rsub__(self,other):if isinstance(other,int):b=other%self.n-self.aif b<0:b+=self.nreturn Modulo(b,self.n, False)def __isub__(self,other):if isinstance(other,Modulo):assert self.n==other.n, "異なる法同士の演算です."y=other.aelif isinstance(other,int):y=other%self.nself.a-=yif self.a<0:self.a+=self.nreturn self#乗法def __mul__(self,other):if isinstance(other,Modulo):assert self.n==other.n, "異なる法同士の演算です."y=other.aelif isinstance(other,int):y=other%self.nreturn Modulo((self.a*y)%self.n, self.n, False)def __rmul__(self,other):if isinstance(other,int):return Modulo((self.a*other)%self.n, self.n, False)def __imul__(self,other):if isinstance(other,Modulo):assert self.n==other.n, "異なる法同士の演算です."y=other.aelif isinstance(other,int):y=other%self.nself.a*=yself.a%=self.nreturn self#Modulo逆数def inverse(self):return self.modulo_inverse()def modulo_inverse(self):s,t=1,0a,b=self.a,self.nwhile b:q,a,b=a//b,b,a%bs,t=t,s-q*tassert a==1,"{}の逆数が存在しません".format(self)s%=self.nreturn Modulo(s,self.n, False)#除法def __truediv__(self,other):return self*(other.modulo_inverse())def __rtruediv__(self,other):return other*(self.modulo_inverse())#累乗def __pow__(self,other):if isinstance(other,int):u=abs(other)r=Modulo(pow(self.a,u,self.n),self.n, False)if other>=0:return relse:return r.modulo_inverse()else:b,n=other.a,other.nassert pow(self.a,n,self.n)==1, "矛盾なく定義できません."return self**b#ルジャンドル記号def Legendre(X):"""ルジャンドル記号 (a/p) を返す.※法が素数のときのみ成立する."""if X==0:return 0elif pow(X,(X.n-1)//2)==1:return 1else:return -1#根号def Sqrt(X, All=False):""" X=a (mod p) のとき, r*r=a (mod p) を満たす r を (存在すれば) 返す.[Input]All: False ならば一方のみ, True ならば両方※ 法 p が素数のときのみ有効※ 存在しないときは None が返り値"""if Legendre(X)==-1:return Nonea,p=X.a,X.nif X==0:return Xelif p==2:return Xelif p%8==3 or p%8==7:r=pow(X,(p+1)//4)if All:return (r,-r)else:return relif p%8==5:if pow(X,(p-1)//4)==1:r=pow(X,(p+3)//8)else:r=pow(2,(p-1)//4,p)*pow(X,(p+3)//8)if All:return (r,-r)else:return rfrom random import randint as riu=2s=1while (p-1)%(2*u)==0:u*=2s+=1q=(p-1)//uz=Modulo(0,p)while pow(z,(p-1)//2)!=-1:z=Modulo(ri(1,p-1),p)m,c,t,r=s,z**q,X**q,pow(X,(q+1)//2)while m>1:if pow(t,2**(m-2))==1:c=c*cm=m-1else:c,t,r,m=c*c,c*c*t,c*r,m-1if All:return (r,-r)else:return r#==================================================def solve():P=int(input())K=(P-1)//2a=Modulo(1,P)b=Modulo(3,P)c=Modulo(K*K+4*K+2, P)D=b*b-4*a*creturn Sqrt(D) is not None#==================================================print("YES" if solve() else "NO")