牛客多校第九场 B Quadratic equation 模平方根

题意：

已知

$x+y$ $mod$ $q = b$

$x*y$ $mod$ $q = c$

已知b和c，求x和y

题解：

容易想到$b^2-4c=x^2-2xy+y^2=(x-y)^2$

那么开个根号就能得到x-y，很容易就得出x和y了

在模q意义下对k开根号的方法就是找到w，使得$w*w$ $mod$ $q=k$

考虑模数q为奇质数的情况，可以用Tonelli-Shanks算法求解，这是一个概率算法，但是一般而言得出正确解的概率非常高，遇到类似问题套版即可。

#include<iostream>
#include<cmath>
#define MOD 1000000007
#define LL long long
using namespace std;
LL  qpow(LL x,LL y,LL m){
    //cal x^y%m
        LL re = 1;
        while(y){
            if(y & 1)//判断n的最后一位是否为1
                re = (re * x) % m;
            y >>= 1;//舍去n的最后一位
            x = (x * x) % m;//将a平方
        }
        return re % m;
    }
class ModSqrt{
    public:
    LL  power(LL x,LL y,LL m){
    //cal x^y%m
        LL re = 1;
        while(y){
            if(y & 1)//判断n的最后一位是否为1
                re = (re * x) % m;
            y >>= 1;//舍去n的最后一位
            x = (x * x) % m;//将a平方
        }
        return re % m;
    }
     
    LL normal_power(LL a,LL b){
        LL re = 1;
        while(b){
            if(b & 1)//判断n的最后一位是否为1
                re = (re * a);
            b>>= 1;//舍去n的最后一位
            a = (a * a);//将a平方
        }
        return re;
    }
     
    LL inverse(LL a,LL m){
        return power(a,m-2,m);
    }
     
    LL getn(LL p){
        for(LL i=2;i<p;i++){
            if(power(i,(p-1)/2,p)==p-1)
                return i;
        }
        return -1;
    }
     
     
    int solve(LL a,LL p){
    
        if(a==0)return 0;
        if(power(a,(p-1)/2,p)==p-1){
            return -1;
        }
        while(a<0)a+=p;
        while(a>p)a-=p;
        LL n=getn(p);
        bool finish=false;
        LL t=1;
        LL s=p-1;
        while(!finish){
            s=s/2;
            if(s%2) finish=true;
            else t+=1;
        }
        LL b=power(n,s,p);
        LL _a=inverse(a,p);
        LL x[66];
        for(LL i=0;i<66;i++)x[i]=0;
        x[t-1]=power(a,(s+1)/2,p); 
        for(LL i=1;i<=t-1;i++){
            LL judge=power((_a*x[t-i]*x[t-i])%p,normal_power(2,t-i-1),p);
            if(judge==1){
                x[t-i-1]=x[t-i];
            }else if(judge==p-1){
                x[t-i-1]=(power(b,normal_power(2,i-1),p)*x[t-i])%p;
            }
        }
        return x[0];
     
    }
}modsqrt;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        LL b,c;
        scanf("%lld %lld",&b,&c);
        LL q=b*b%MOD-4*c%MOD;
        q=(q+MOD)%MOD;
        LL sq=modsqrt.solve(q,MOD);
        if(sq==-1)printf("-1 -1
");
        else{
            LL xx=sq+b;
            LL yy=(b-sq+MOD)%MOD;
            LL x=xx*qpow(2,MOD-2,MOD)%MOD;
            LL y=yy*qpow(2,MOD-2,MOD)%MOD;
            if(x>y)swap(x,y);
            printf("%lld %lld
",x,y);
        }
    }
    return 0;
}