結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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")
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0