发布时间：2025-05-22

二次剩余

给出$N,p$，求解$x^2 \equiv N(\mod p)$的两个解

int cipolla(int x,int P){
    x%=P;
    if(!x)return 0;
    if(qpow(x,P-1>>1,P)==P-1)return -1;
    while(1){
        int a=rng()%P;
        int w=(a*a%P-x+P)%P;
        const auto mul=[&](PII a,PII b){
            return PII{(a.F*b.F%P+w*a.S%P*b.S%P)%P,(a.F*b.S%P+a.S*b.F%P)%P};
        };
        const auto pow=[&](PII a,int b){
            PII res{1,0};
            for(;b;b>>=1){
                if(b&1)res=mul(res,a);
                a=mul(a,a);
            }
            return res.F;
        };
        if(qpow(w,P-1>>1,P)==P-1){
            int res=pow(PII{a,1},P+1>>1);
            return min(res,P-res);
        }
    }
}
void solve(){
    int n,p;
    cin>>n>>p;
    int res=cipolla(n,p);
    if(res==-1)cout<<"Hola!\n";
    else{
        int ans=(p-res)%p;
        if(ans>res)swap(ans,res);
        if(ans==res)cout<<ans<<"\n";
        else cout<<ans<<" "<<res<<"\n";
    }
}