[ural1132]Square Root(cipolla算法)

题意：求${x^2} equiv nmod p$

解题关键：

定理：若$a$满足$w = {a^2} - n$是模$p$的二次非剩余，即，${x^2} = wmod p$无解，则${(a + sqrt w )^{frac{{p + 1}}{2}}}$是二次剩余方程${x^2} equiv nmod p$的解。

证明：

$egin{array}{l}
{x^2} equiv {(a + sqrt w )^{p + 1}} equiv (a + sqrt w ){(a + sqrt w )^p}\
equiv (a + sqrt w )(sum {C_p^i{a^{p - i}}{w^{frac{i}{2}}}} )\
equiv (a + sqrt w )({a^p} + {w^{frac{{p - 1}}{2}}}sqrt w )\
equiv (a + sqrt w )(a - sqrt w )\
equiv n(mod p)
end{array}$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
ll w,a,x,p,T;
struct CN{
    ll x,y;
    CN friend operator *(CN x,CN y){
        CN z;
        z.x=(x.x*y.x+x.y*y.y*w)%p;
        z.y=(x.x*y.y+x.y*y.x)%p;
        return z;
    }
};

CN Cmod_pow(CN x,ll n){
    CN z={1,0};
    while(n){
        if(n&1)z=z*x;
        x=x*x;
        n>>=1;
    }
    return z;
}

ll mod_pow(ll x,ll n,ll p){
    ll res=1;
    while(n){
        if(n&1) res=res*x%p;
        x=x*x%p;
        n>>=1;
    }
    return res;
}

int main(){
    scanf("%lld",&T);
    while(T--){
        scanf("%lld%lld",&x,&p);
        x%=p;
        if(p==2){
            printf("1
");
            continue;
        }
        if(mod_pow(x,(p-1)/2,p)==p-1){
            printf("No root
");
            continue;
        }
        while(1){
            a=rand()%p;
            w=(a*a-x+p)%p;
            if(mod_pow(w,(p-1)/2,p)==p-1) break;
        }
        
        CN u={a,1};
        u=Cmod_pow(u,(p+1)/2);
        ll yi=u.x,er=p-u.x;
        if(yi>er) printf("%lld %lld
",er,yi);
        else if(yi==er) printf("%lld
",yi);
        else printf("%lld %lld
",yi,er);
    }
}