結果

問題 No.2191 一元二次式 mod 奇素数
ユーザー 👑 KazunKazun
提出日時 2023-01-13 21:44:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 137 ms / 2,000 ms
コード長 6,285 bytes
コンパイル時間 130 ms
コンパイル使用メモリ 81,648 KB
実行使用メモリ 55,296 KB
最終ジャッジ日時 2024-06-06 22:22:24
合計ジャッジ時間 1,989 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 32 ms
53,248 KB
testcase_01 AC 36 ms
53,120 KB
testcase_02 AC 38 ms
53,248 KB
testcase_03 AC 36 ms
53,504 KB
testcase_04 AC 37 ms
53,248 KB
testcase_05 AC 137 ms
55,168 KB
testcase_06 AC 35 ms
53,376 KB
testcase_07 AC 33 ms
53,248 KB
testcase_08 AC 33 ms
53,248 KB
testcase_09 AC 33 ms
52,908 KB
testcase_10 AC 32 ms
53,632 KB
testcase_11 AC 33 ms
53,632 KB
testcase_12 AC 35 ms
55,296 KB
testcase_13 AC 33 ms
53,248 KB
testcase_14 AC 32 ms
52,992 KB
testcase_15 AC 32 ms
53,376 KB
testcase_16 AC 35 ms
53,248 KB
testcase_17 AC 34 ms
53,376 KB
testcase_18 AC 38 ms
53,504 KB
testcase_19 AC 35 ms
53,248 KB
testcase_20 AC 37 ms
53,504 KB
testcase_21 AC 37 ms
53,120 KB
testcase_22 AC 36 ms
53,376 KB
testcase_23 AC 44 ms
55,168 KB
testcase_24 AC 37 ms
53,376 KB
testcase_25 AC 35 ms
53,504 KB
testcase_26 AC 40 ms
55,040 KB
権限があれば一括ダウンロードができます

ソースコード

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