二次剩余模板

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Field {
    ll mod = 1000000007;
    //扩域 first实部 second虚部
    typedef pair<ll, ll> pll;
    ll qpow_num(ll a, ll b) {
        ll ans = 1;
        while (b) {
            if (b & 1) {
                ans = (ans * a) % mod;
            }
            b >>= 1;
            a = (a * a) % mod;
        }
        return ans % mod;
    }
    //扩域相乘 
    pll qmul_pll(pll a, pll b, ll w) {
        pll ans;
        ans.first = ((a.first * b.first) % mod + ((a.second * b.second) % mod * w) % mod) % mod;
        ans.second = ((a.second * b.first) % mod + (a.first * b.second) % mod) % mod;
        return ans;
    }
    //扩域快速幂
    pll qpow_pll(pll a, ll b, ll w) {
        pll ans = make_pair(1, 0);
        while (b) {
            if (b & 1) {
                ans = qmul_pll(ans, a, w);
            }
            a = qmul_pll(a, a, w);
            b >>= 1;
        }
        return ans;
    }
    //求x^2%p=n（求n的二次剩余） 
    ll solve(ll n, ll p) {
        mod = p;
        n %= mod;
        if (n <= 1) return n;
        if (mod == 2) return n;
        if (qpow_num(n, (mod - 1) / 2) == mod - 1) return -1;
        ll a, w;
        while (1) {
            a = rand() % mod;
            w = ((a * a - n) % mod + mod) % mod;
            if (qpow_num(w, (mod - 1) / 2) == mod - 1) break;
        }
        pll ans = make_pair(a, 1);
        return qpow_pll(ans, (mod + 1) / 2, w).first;
    }
}field;
ll getans(ll a, ll b, ll &x, ll &y) {
    if ((a + b) % 2 == 0) {
        y = (a + b) / 2;
        x = y - a;
        if (x >= 0 && y >= 0 && x < field.mod && y < field.mod) return true;
    }
    return false;
}

int main() {
    int T;
    srand(time(0));
    cin >> T;
    while (T--) {
        ll b, c, p = 1000000007;
        cin >> b >> c;
        ll n = b * b - 4 * c + p;
        n = (n % p + p) % p;
        ll ans1 = field.solve(n, p);    
        if (ans1 == -1) {
            cout << "-1 -1" << endl; continue;
        }
        ll ans2 = p - ans1;
        ll x, y;
        if (getans(ans1, b, x, y)) {
            cout << x << " " << y << endl; continue;
        }
        if (getans(ans1, b + p, x, y)) {
            cout << x << " " << y << endl; continue;
        }
        if (getans(ans2, b, x, y)) {
            cout << x << " " << y << endl; continue;
        }
        if (getans(ans2, b + p, x, y)) {
            cout << x << " " << y << endl; continue;
        }
        cout << "-1 -1" << endl;

    }
    return 0;
}