2019牛客暑期多校训练营（第九场）B：Quadratic equation （二次剩余求mod意义下二元一次方程）

题意：给定p=1e9+7，A，B。  求一对X，Y，满足（X+Y）%P=A; 且（X*Y）%P=B；

思路：即，X^2-BX+CΞ0;  那么X=[B+-sqrt(B^2-4C)]/2；

全部部分都要在modP意义下，所以求一个x满足x^2%p=B^2-4C，这个用二次剩余求即可。

套了模板。

#include <bits/stdc++.h>

using namespace std;

const int mod=1e9+;

typedef long long ll;

int k; ll a,p,w;

struct T{ll x,y;};

T mul_two(T a,T b,ll p)

{

    T ans;

    ans.x=(a.x*b.x%p+a.y*b.y%p*w%p)%p;

    ans.y=(a.x*b.y%p+a.y*b.x%p)%p;

    return ans;

}

T qpow_two(T a,ll n,ll p)

{

    T ans; ans.x=; ans.y=;

    while(n){

        if(n&) ans=mul_two(ans,a,p);

        n>>=;

        a=mul_two(a,a,p);

    }

    return ans;

}

ll qpow(ll a,ll n,ll p)

{

    ll ans=; a%=p;

    while(n){

        if(n&) ans=ans*a%p;

        n>>=;a=a*a%p;

    }

    return ans%p;

}

ll Legendre(ll a,ll p)

{

    return qpow(a,(p-)>>,p);

}

int solve(ll n,ll p)

{

    n%=p; if(p==) return ;

    if(Legendre(n,p)+==p) return -;

    else if(n==) return ;

    ll a=;

    while(Legendre((a*a-n+p)%p,p)+!=p)  a=rand()%p;

    T tmp; tmp.x=a; tmp.y=; w=(a*a-n+p)%p;//W

    T ans=qpow_two(tmp,(p+)>>,p);

    return ans.x;

}

int main()

{

    scanf("%d",&k); ll rev2=;

    while(k--){

        ll b,c;

        scanf("%lld%lld",&b,&c);

        ll t=((b*b-c*)%mod+mod)%mod;

        ll d=solve(t,mod);

        if(d==-){

            printf("-1 -1\n");

            continue;

        }

        ll x=(b+d)*rev2%mod,y=(b-x+mod)%mod;

        if(x>y) swap(x,y);

        printf("%lld %lld\n",x,y);

    }

    return ;

}