原题链接

https://www.luogu.com.cn/problem/P5491

二次剩余用于解决这类问题：求解方程$x ^ 2 ≡ n (mod$ $p)$，其中大部分情况下$p$为奇质数。

首先随机取一个$a$使得$a^2-n$不是模$p$意义下的二次剩余。

用复数的思想，定义单位根使得$i ^ 2 ≡ a ^ 2 - n$

由于勒让德符号定义，$i ^ p = i × (i ^ 2) ^ \frac{p - 1}{2} = i × (a ^ 2 - n) ^ \frac{p - 1}{2} = - i$

且根据二项式定理，$(a + b)^p ≡ a^p + b^p(mod$ $p)$

∴ $(a+i)^ {p+1} ≡(a^p+i^p)(a+i) ≡a^2-i^2=n$

所以$(a+i)^\frac{p+1}{2}$为一个根，相反数为另一个

代码如下

#include <cstdio>
#include <algorithm>
#include <cstring>

#define int long long

using namespace std;

const int N = 1e5 + 20;

int n, T, p, I;

int ksm(int x, int y, int p)
{
    x %= p;
    int s = 1;
    while(y)
    {
        if(y & 1) s = s * x % p;
        x = x * x % p;
        y >>= 1;
    }
    return s;
}

int lrd(int a, int p)
{
    return ksm(a, (p - 1) / 2, p) == 1;
}

struct Comp
{
    int x, y;
}A, S;

Comp operator * (Comp a, Comp b)
{
    Comp c;
    c.x = (a.x * b.x + I * a.y % p * b.y % p) % p;
    c.y = (a.x * b.y + a.y * b.x) % p;
    return c;
}

int Ksm(Comp a, int y)
{
    Comp s; s.x = 1; s.y = 0;
    while(y)
    {
        if(y & 1) s = s * a;
        a = a * a;
        y >>= 1;
    }
    return s.x;
}

signed main()
{
    scanf("%lld", &T);
    while(T --)
    {
        scanf("%lld%lld", &n, &p);
        if(n == 0)
        {
            printf("0\n"); continue;
        }
        if(!lrd(n, p))
        {
            puts("Hola!"); continue;
        }
        int a;
        while(1)
        {
            a = rand() % p;
            I = (a * a - n);
            I = (I % p + p) % p;
            if(lrd(I, p) || !a) continue;
            break;
        }
        Comp g; g.x = a; g.y = 1;
        int x_1 = Ksm(g, (p + 1) / 2);
        int x_2 = (p - x_1) % p;
        if(x_1 > x_2) swap(x_1, x_2);
        if(x_1 == x_2) printf("%lld\n", x_1);
        else printf("%lld %lld\n", x_1, x_2);
    }
    return 0;
}