二次剩余

定义

对于任意正整数\(n\)，若对于一个质数\(p\),存在\(x\)满足\(x^2≡n \pmod p\)则称\(n\)是模\(p\)的二次剩余

用来在模意义下开根

求法

\(rand\)一个\(a\),使得\(\frac{(a^2-n)}p\equiv-1\pmod p\)（即\((a^2-n)^{\frac{p-1}2}\equiv-1\pmod p\)）

定义\(w=\sqrt{a^2-n}\)为虚数单位。

答案即为\(x\equiv(a+w)^{\frac{p+1}2}\pmod p\)

当\(n^{\frac {p-1}2}\equiv-1\pmod p\)时无解（这个参见勒让德符号）。

证明:

易证\(w^p=-w\)

\(x^2=(a+w)^{p+1}=(a+w)^p(a+w)=(a^p+w^p)(a+w)=(a-w)(a+w)=a^2-w^2=n\)

洛谷\(P5491AC\)代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IL inline
#define RG register
#define gi geti<int>()
#define gl geti<ll>()
#define gc getchar()
#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
template<typename T>IL bool chkmax(T &x,const T &y){return x<y?x=y,1:0;}
template<typename T>IL bool chkmin(T &x,const T &y){return x>y?x=y,1:0;}
template<typename T>
IL T geti()
{
    RG T xi=0;
    RG char ch=gc;
    bool f=0;
    while(!isdigit(ch))ch=='-'?f=1:f,ch=gc;
    while(isdigit(ch))xi=xi*10+ch-48,ch=gc;
    return f?-xi:xi;
}
template<typename T>
IL void pi(T k,char ch=0)
{
    if(k<0)k=-k,putchar('-');
    if(k>=10)pi(k/10);
    putchar(k%10+'0');
    if(ch)putchar(ch);
}
ll sqrI,P;
template<typename T>
IL T ksm(T a,int b,ll Mod=1)
{
    T ret=a;
    for(--b;b;b>>=1,a=a*a%Mod)
        if(b&1)ret=ret*a%Mod;
    return ret;
}
#define complex _complex
struct complex{
    ll x,y;
};
complex operator * (const complex &a,const complex &b)
{
    return (complex){a.x*b.x%P+a.y*b.y%P*sqrI%P,a.x*b.y%P+a.y*b.x%P};
}
complex operator % (const complex &a,ll Mod)
{
    return (complex){a.x%Mod,a.y%Mod};
}
inline ll solve(ll n,ll p)
{
    n%=p,P=p;
    if(p==2)return n;
    if(ksm(n,(p-1)>>1,p)==p-1)return -1;
    ll a;
    while(1)
    {
        a=rand()%P;
        sqrI=((a*a%P-n)%P+P)%P;
        if(ksm(sqrI,(P-1)>>1,P)==P-1)break;
    }
    return ksm((complex){a,1},(p+1)>>1,P).x;
}
#undef complex
int main(void)
{
    srand(19260817);
    int T=gi;
    while(T--)
    {
        ll n=gl,p=gl;
        if(!n)puts("0");
        else{
            ll ans1=solve(n,p),ans2;
            if(~ans1){
                ans2=p-ans1;
                if(ans1>ans2)swap(ans1,ans2);
                if(ans1==ans2)pi(ans1,'\n');
                else pi(ans1,' '),pi(ans2,'\n');
            }
            else puts("Hola!");
        }
    }
    return 0;
}