結果
| 問題 | No.2191 一元二次式 mod 奇素数 |
| ユーザー |
👑  Kazun
|
| 提出日時 | 2023-01-13 21:44:49 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 91 ms / 2,000 ms |
| コード長 | 6,285 bytes |
| コンパイル時間 | 304 ms |
| コンパイル使用メモリ | 87,140 KB |
| 実行使用メモリ | 72,200 KB |
| 最終ジャッジ日時 | 2023-08-26 03:26:20 |
| 合計ジャッジ時間 | 3,614 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 72 ms
71,200 KB |
| testcase_01 | AC | 71 ms
71,440 KB |
| testcase_02 | AC | 72 ms
71,220 KB |
| testcase_03 | AC | 72 ms
71,324 KB |
| testcase_04 | AC | 73 ms
71,196 KB |
| testcase_05 | AC | 91 ms
72,136 KB |
| testcase_06 | AC | 71 ms
71,320 KB |
| testcase_07 | AC | 75 ms
71,348 KB |
| testcase_08 | AC | 74 ms
71,332 KB |
| testcase_09 | AC | 72 ms
71,420 KB |
| testcase_10 | AC | 73 ms
71,328 KB |
| testcase_11 | AC | 72 ms
71,332 KB |
| testcase_12 | AC | 89 ms
72,096 KB |
| testcase_13 | AC | 71 ms
71,396 KB |
| testcase_14 | AC | 71 ms
71,308 KB |
| testcase_15 | AC | 71 ms
71,396 KB |
| testcase_16 | AC | 73 ms
71,236 KB |
| testcase_17 | AC | 73 ms
71,468 KB |
| testcase_18 | AC | 72 ms
71,392 KB |
| testcase_19 | AC | 73 ms
71,424 KB |
| testcase_20 | AC | 72 ms
71,440 KB |
| testcase_21 | AC | 73 ms
71,192 KB |
| testcase_22 | AC | 73 ms
71,484 KB |
| testcase_23 | AC | 91 ms
72,020 KB |
| testcase_24 | AC | 73 ms
71,224 KB |
| testcase_25 | AC | 72 ms
71,456 KB |
| testcase_26 | AC | 90 ms
72,200 KB |
ソースコード
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")