题意：

求\(x^2 \equiv a \mod p\) 的所有整数解

思路：

二次剩余定理求解。

参考：

二次剩余Cipolla's algorithm学习笔记

板子：

//二次剩余，p是奇质数

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;

}

代码：

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

}

int main(){

    int T;

    scanf("%d", &T);

    while(T--){

        ll a, n;

        scanf("%lld%lld", &a, &n);

        ll ans1 = solve(a, n), ans2;

        if(ans1 == -1){

            printf("No root\n");

            continue;

        }

        ans2 = n - ans1;

        if(ans1 > ans2) swap(ans1, ans2);

        if(ans1 == ans2) printf("%lld\n", ans1);

        else printf("%lld %lld\n", ans1, ans2);

    }

    return 0;

}