結果
| 問題 |
No.2191 一元二次式 mod 奇素数
|
| コンテスト | |
| ユーザー |
👑  Kazun
|
| 提出日時 | 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%=n
self.a=a
self.n=n
def __str__(self):
return "{} (mod {})".format(self.a, self.n)
def __repr__(self):
return self.__str__()
#+,-
def __pos__(self):
return self
def __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==0
def __neq__(self,other):
return not(self==other)
def __le__(self,other):
a,p=self.a,self.n
b,q=other.a,other.n
return (a-b)%q==0 and p%q==0
def __ge__(self,other):
return other<=self
def __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.a
elif isinstance(other,int):
y=other%self.n
b=self.a+y
if self.n<=b:
b-=self.n
return 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.n
return Modulo(b,self.n, False)
def __iadd__(self,other):
if isinstance(other,Modulo):
assert self.n==other.n, "異なる法同士の演算です."
y=other.a
elif isinstance(other,int):
y=other%self.n
self.a+=y
if self.a>=self.n:
self.a-=self.n
return self
#減法
def __sub__(self,other):
if isinstance(other,Modulo):
assert self.n==other.n, "異なる法同士の演算です."
y=other.a
elif isinstance(other,int):
y=other%self.n
b=self.a-y
if b<0:
b+=self.n
return Modulo(b,self.n, False)
def __rsub__(self,other):
if isinstance(other,int):
b=other%self.n-self.a
if b<0:
b+=self.n
return Modulo(b,self.n, False)
def __isub__(self,other):
if isinstance(other,Modulo):
assert self.n==other.n, "異なる法同士の演算です."
y=other.a
elif isinstance(other,int):
y=other%self.n
self.a-=y
if self.a<0:
self.a+=self.n
return self
#乗法
def __mul__(self,other):
if isinstance(other,Modulo):
assert self.n==other.n, "異なる法同士の演算です."
y=other.a
elif isinstance(other,int):
y=other%self.n
return 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.a
elif isinstance(other,int):
y=other%self.n
self.a*=y
self.a%=self.n
return self
#Modulo逆数
def inverse(self):
return self.modulo_inverse()
def modulo_inverse(self):
s,t=1,0
a,b=self.a,self.n
while b:
q,a,b=a//b,b,a%b
s,t=t,s-q*t
assert a==1,"{}の逆数が存在しません".format(self)
s%=self.n
return 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 r
else:
return r.modulo_inverse()
else:
b,n=other.a,other.n
assert pow(self.a,n,self.n)==1, "矛盾なく定義できません."
return self**b
#ルジャンドル記号
def Legendre(X):
"""ルジャンドル記号 (a/p) を返す.
※法が素数のときのみ成立する.
"""
if X==0:
return 0
elif pow(X,(X.n-1)//2)==1:
return 1
else:
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 None
a,p=X.a,X.n
if X==0:
return X
elif p==2:
return X
elif p%8==3 or p%8==7:
r=pow(X,(p+1)//4)
if All:
return (r,-r)
else:
return r
elif 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 r
from random import randint as ri
u=2
s=1
while (p-1)%(2*u)==0:
u*=2
s+=1
q=(p-1)//u
z=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*c
m=m-1
else:
c,t,r,m=c*c,c*c*t,c*r,m-1
if All:
return (r,-r)
else:
return r
#==================================================
def solve():
P=int(input())
K=(P-1)//2
a=Modulo(1,P)
b=Modulo(3,P)
c=Modulo(K*K+4*K+2, P)
D=b*b-4*a*c
return Sqrt(D) is not None
#==================================================
print("YES" if solve() else "NO")