题意：

传送门

已知\(0 <= x <= y < p, p = 1e9 + 7\)且有

\((x+y) = b\mod p\)

\((x\times y)=c\mod p\)

求解任意一对\(x,y\)，不存在输出\(-1\ -1\)。

思路：

由两式变化可得\((y - x)^2 = (b^2 -4c + p) \% p \mod p\)，那么可以应用二次剩余定理解得\(y - x\)的值，我们可以知道\((x+y) = b\)或者\((x+y) = b + p\)，那么直接求解即可。

代码：

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<ctime>

#include<cmath>

#include<cstdio>

#include<string>

#include<vector>

#include<cstring>

#include<sstream>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int maxn = 5e4 + 5;

const int INF = 0x3f3f3f3f;

const ull seed = 131;

const ll MOD = 1e9 + 7;

using namespace std;

ll ppow(ll a, ll b, ll mod){

    ll ret = 1;

    a = a % mod;

    while(b){

        if(b & 1) ret = ret * a % mod;

        a = a * a % mod;

        b >>= 1;

    }

    return ret;

}

struct TT{

    ll p, d;

};

ll w;

TT mul_er(TT a, TT b, ll mod){

    TT ans;

    ans.p = (a.p * b.p % mod + a.d * b.d % mod * w % mod) % mod;

    ans.d = (a.p * b.d % mod + a.d * b.p % mod) % mod;

    return ans;

}

TT power(TT a, ll b, ll mod){

    TT ret;

    ret.p = 1, ret.d = 0;

    while(b){

        if(b & 1) ret = mul_er(ret, a, mod);

        a = mul_er(a, a, mod);

        b >>= 1;

    }

    return ret;

}

ll legendre(ll a, ll p){

    return ppow(a, (p - 1) >> 1, p);

}

ll modulo(ll a, ll mod){

    a %= mod;

    if(a < 0) a += mod;

    return a;

}

ll solve(ll n, ll p){   //x^2 = n mod p

    if(n == 0) return 0;

    if(n == 1) return 1;

    if(p == 2) return 1;

    if(legendre(n, p) + 1 == p) return -1;  //无解

    ll a = -1, t;

    while(true){

        a = rand() % p;

        t = a * a - n;

        w = modulo(t, p);

        if(legendre(w, p) + 1 == p) break;

    }

    TT temp;

    temp.p = a;

    temp.d = 1;

    TT ans = power(temp, (p + 1) >> 1, p);

    return ans.p;

}

bool getans(ll sum, ll dec, ll &x, ll &y){

    if((sum + dec) % 2 == 0){

        y = (sum + dec) / 2;

        x = y - dec;

        if(x >= 0 && x + y == sum && y < MOD) return true;

        else return false;

    }

    else return false;

}

int main(){

    int T;

    scanf("%d", &T);

    while(T--){

        ll b, c;

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

        ll d = solve((b * b % MOD - 4 * c % MOD + MOD) % MOD, MOD);

        if(d == -1){

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

            continue;

        }

        ll x, y;

        if(getans(b, d, x, y)){

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

        }

        else if(getans(b + MOD, d, x, y)){

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

        }

        else if(getans(b, MOD - d, x, y)){

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

        }

        else if(getans(b + MOD, MOD - d, x, y)){

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

        }

    }

    return 0;

}

巴特西

2019牛客多校第九场B Quadratic equation（二次剩余定理）题解

题意：

思路：

代码：

最新文章

热门文章