2019牛客暑期多校训练营（第九场） - B - Quadratic equation

https://ac.nowcoder.com/acm/contest/889/B

假如我们能够求出 \(x-y\) 在模p意义的值，那么就可以和 \(x+y\) 联立解出来了。

由于 \((x-y)^2=(x+y)^2-4xy=b^2-4c\) ，那么设 \(n=b^2-4c\) ，就是要求解出一个二次剩余。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int p = 1e9 + 7;

struct hh {

    ll x, y;

    hh() {};

    hh(ll _x, ll _y) {

        x = _x;

        y = _y;

    }

};

ll w;

hh mul(hh a, hh b, ll p) {

    hh 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;

}

hh quick1(hh a, ll b, ll p) {

    hh ans = hh(1, 0);

    while(b) {

        if(b & 1)

            ans = mul(ans, a, p);

        a = mul(a, a, p);

        b >>= 1;

    }

    return ans;

}

ll quick2(ll a, ll b, ll p) {

    ll ans = 1;

    while(b) {

        if(b & 1)

            ans = (ans * a) % p;

        b >>= 1;

        a = (a * a) % p;

    }

    return ans;

}

ll solve(ll a, ll p) { //求解 x^2=a(mod p) 的x的值

    a %= p; //注意这句话

    if(a == 0)

        return 0;//注意这句话

    if(p == 2)

        return a;

    if(quick2(a, (p - 1) / 2, p) == p - 1)

        return -1;

    ll b, t;

    while(1) {

        b = rand() % p;

        t = b * b - a;

        w = (t % p + p) % p;

        if(quick2(w, (p - 1) / 2, p) == p - 1)

            break;

    }

    hh ans = hh(b, 1);

    ans = quick1(ans, (p + 1) / 2, p);

    return ans.x;

}

ll qpow(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;

}

ll x, y;

void solvexy(ll b, ll d) {

    y = (b + d) % p * qpow(2, p - 2, p) % p;

    x = (b - y + p) % p;

    if(x > y)

        swap(x, y);

    return;

}

int main() {

#ifdef Yinku

    freopen("Yinku.in", "r", stdin);

#endif // Yinku

    int t;

    scanf("%d", &t);

    while (t--) {

        ll b, c;

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

        ll n = b * b - 4ll * c;

        n = (n % p + p) % p;

        ll d = solve(n, p);

        if (d == -1)

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

        else {

            solvexy(b, d);

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

        }

    }

}

巴特西

2019牛客暑期多校训练营（第九场） - B - Quadratic equation - 二次剩余

最新文章

热门文章