P5491 【模板】二次剩余 题解

· · 题解

二次剩余，是数论中的一大板块。

首先了解一下二次剩余的定义： 如果一个数 n 是模 p 的二次剩余，那么就存在数 x 满足 n \equiv x^2 \pmod p。

关于二次剩余的符号:

勒让德符号 (\dfrac a b)

当 (\dfrac a b)=1 时: a \neq 0 且 a 是模 b 意义下的二次剩余。

当 (\dfrac a b)=0 时: a = 0 ( a 也是模 b 意义下的二次剩余。)

当 (\dfrac a b)=-1 时: a \neq 0 且 a 不是模 b 意义下的二次剩余。

欧拉判定

欧拉判定：(\dfrac n p) \equiv n^{\frac{p-1} {2} } \pmod p

欧拉判定可以用于 O(\log p) 判断是否是二次剩余。

Cippola

Cippola 是以一种特别玄学的方式求出一个数模意义下开的根。像 PollardRho 一样，通过随机的枚举来进行寻找。

$\space\space$ 首先不停地随机一个数 $k$,知道找到一个 $t$ 使 $t^2-n$ 不是模 $p$ 的二次剩余。 $\space\space$ 显然，这个数是没有模 $n$ 意义下的根。所以，我们自己定义 $w \equiv \sqrt{t^2-n} \pmod n$。 $\space\space$ 接下来，有： $$w^p \equiv w \times w^{p-1} \equiv w \times (w^2)^{\frac {p-1} 2} \equiv w \times (t^2-n)^{\frac{p-1} 2} \equiv w \times (t^2-n)^{\frac {p-1} 2} \pmod p$$ $\space\space$ 因为 $t^2-n$ 不是模 $p$ 的二次剩余,所以 $(t^2-n)^{\frac {p-1} 2} \equiv -1 \pmod p \space\space$ 所以 $w \times (t^2-n)^{\frac {p-1} 2} \equiv -w\pmod p \space\space$ 所以 $w^p \equiv -w \pmod p \space\space$ 接下来证明一个定理： $a^p+b^p \equiv (a+b)^p \pmod p \space\space$ 首先由二项式定理,$(a+b)^p=\sum_0^p C^i_{p-i}a^ib^{p-i} $\space\space$ 所以，$a^p+b^p \equiv (a+b)^p \pmod p

证明完毕。

接下来，记答案为 x,则

x^2 \equiv (a+w)^{p+1}\pmod p \equiv(a+w)^p\times (a+w) \equiv(a^p+w^p)\times (a+w)

又因为 a^p \equiv a\pmod p,

(a^p+w^p)\times (a+w)\equiv(a-w)\times (a+w) \pmod p \space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\equiv a^2-w^2 \pmod p \space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\equiv a^2-(a^2-n)\pmod p \space\space\space\space\space\space\space\space\equiv n\pmod p

所以，令 x=(a+w)^{\frac {p+1} 2} 即可

在这篇让人看不懂的题解的最后，附上看人品 AC 的代码:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define int long long
struct Complex{
    int x,y;
    Complex(int a=0,int b=0){x=a;y=b;}
};
int W;
int mod;
Complex operator+(const Complex &a,const Complex &b){return Complex((a.x+b.x)%mod,(a.y+b.y)%mod);}
Complex operator*(const Complex &a,const Complex &b){return Complex((a.x*b.x%mod+a.y*b.y%mod*W%mod)%mod,(a.x*b.y+a.y*b.x)%mod);}
int qpow(int a,int b,int p){
    int ans=1,base=a;a%=p;if(a<0)a+=p;
    for(;b;b>>=1){
        if(b&1)ans=ans*base%p;
        base=base*base%p;
    }
    return ans;
}
Complex qpow(Complex a,int b,int p){
    mod=p;
    Complex ans(1,0),base=a;
    for(;b;b>>=1){
        if(b&1)ans=ans*base;
        base=base*base;
    }
    return ans;
}
Complex judge(int x,int p){return qpow(x,(p-1)>>1,p);}
void solve(){
    int x,p;
    scanf("%lld%lld",&x,&p);
    int q=qpow(x,(p-1)>>1,p);
    if(q==0){
        puts("0");
        return;
    }
    if(q==p-1){
        puts("Hola!");
        return;
    }
    int rd=rand()%p;
    while(qpow(rd*rd-x+p,(p-1)>>1,p)!=p-1)rd=rand()%p;
    Complex t(rd,1);W=(rd*rd-x+p)%p;
    t=qpow(t,(p+1)>>1,p);
    int ans1=(t.x+p)%p,ans2=(p-ans1)%p;
    if(ans1==ans2)printf("%lld\n",ans1);
    else if(ans1<ans2)printf("%lld %lld\n",ans1,ans2);
    else printf("%lld %lld\n",ans2,ans1);
} 
signed main(){
    srand(time(0));
    int T;
    scanf("%lld",&T);
    while(T--)solve();
}