题意

给定一个正整数 $n$，解方程

$$x^2 \equiv n \pmod{p}$$

这里只考虑 $p$ 为奇素数的情况。

解的个数

假设对于 $n$ 有多个解，其中两个为 $x_1$ 和 $x_2$。

那么有

$$x_1^2 - x_2^2 \equiv 0\pmod{p}$$

$$(x_1 - x_2)(x_1 + x_2) \equiv 0\pmod{p}$$

因为 $x_1 \ne x_2$，那么 $x_1$ 和 $x_2$ 就一定是相反数，所以对于一个 $n$ 要么有两个解，要么无解。

如果对于 $n$ 有两个解，则称它为二次剩余，否则为二次非剩余。

顺带一提，因为一对相反数只能构成一个二次剩余，所以二次剩余的个数为 $\frac{p-1}{2}$ 个。

Legendre 符号

$\left(\frac{a}{p}\right)=\left \{\begin{array}{l} 0, & p\mid a, \\ 1, & (p\nmid a) \wedge ((\exists x \in Z), x^2\equiv a\pmod{p}), \\ -1, & otherwise.\\ \end{array}\right.$

欧拉准则

对于奇素数 $p$ 和正整数 $a$，有

$$a^{\frac{p-1}{2}} \equiv \left(\frac{a}{p}\right) \pmod{p}$$

接下来我们证明一下这个结论，设 $g$ 为 $p$ 的一个原根，且有 $g^q \equiv a \pmod{p}$。

引理1

若 $a$ 为二次剩余，当且仅当 $q$ 为偶数。

先证明充分性

若 $q$ 为偶数，那么就有一个解为 $g^{\frac{q}{2}}$，即 $a$ 为二次剩余。

再证明必要性

设 $x = g^{y}$ 为 $x^2\equiv a\pmod{p}$ 的一个解，那么就有

$$g^{2y} \equiv g^q \pmod{p}$$

$$2y \equiv q\pmod{\varphi(p)}$$

因为 $2y$ 和 $\varphi(p)$ 都是偶数，所以 $q$ 也一定是偶数。

证明

那么有

$$a^{\frac{p-1}{2}} \equiv (g^{\frac{p-1}{2}})^q \equiv (-1)^q \pmod{p}$$

根据引理1得出的结论，若 $a$ 为二次剩余，则 $q$ 为偶数，否则为奇数，所以 $(-1)^q \equiv \left(\frac{a}{p}\right) \pmod{p}$。

证毕。

Cipolla 算法

我们先找到一个 $a$，使得 $a^2 - n$ 是二次非剩余，由于二次非剩余出现概率为 $\frac{1}{2}$，所以用随机数很容易得到一个合适的 $a$。

根据欧拉准则，有 $(a^2-n)^{\frac{p-1}{2}} \equiv -1 \pmod{p}$。

我们重新定义一个虚数概念，将虚数单位 $i$ 定义为 $i^2 \equiv a^2 - n\pmod{p}$，将所有虚数表示为 $A + Bi$ 的形式（$A,B\in R$），并且认为模 $p$ 意义下的虚数为对于 $A,B$ 分别取模。

引理1

$i^p\equiv -i\pmod{p}$

证明：$i^p \equiv i (i^2)^{\frac{p-1}{2}} \equiv i (a^2 - n)^{\frac{p-1}{2}} \equiv -i \pmod{p}$

引理2

$(A+B)^p \equiv A^p + B^p \pmod{p}$

证明：运用二项式定理，只有 $C_p^0$ 和 $C_p^p$ 不是 $p$ 的倍数，所以等于 $A^p + B^p$。

有了以上引理，进行计算 $(a+i)^{p+1} \equiv (a+i)^p (a+i) \equiv (a^p + i^p)(a+i) \equiv (a-i)(a+i) \equiv a^2 - i^2 \equiv n \pmod{p}$，于是我们得到一个解 $(a+i)^{\frac{p + 1}{2}}$。

这时我们有一个疑问，这个数一定是实数吗？

运用反证法，设存在一个虚数解 $A + Bi$ 满足方程 $(A+Bi)^2 \equiv n \pmod{p}（B\ne 0）$，

那么有 $A^2 + B^2i^2 + 2ABi \equiv n \pmod{p}$，

$A^2 + B^2(a^2 - n) - n \equiv 2ABi \pmod{p}$

由于方程左边不是虚数，所以右边也一定不是虚数，即 $A=0$，于是 $(Bi)^2 \equiv n\pmod{p}$，

得到 $i^2 \equiv n B^{-2}\pmod{p}$ 由于 $n$ 和 $B^{-2}$ 均为二次剩余，所以右边一定为二次剩余，而左边不是，矛盾，假设不成立。

所以得出的解一定是实数。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll I_mul_I, mod;

struct Complex {
    ll a, b;
    Complex operator* (Complex y) {
        return {(a * y.a % mod + b * y.b % mod * I_mul_I % mod) % mod, (a * y.b % mod + b * y.a % mod) % mod};
    }
};

ll qpow(ll x, ll y) {
    ll res = 1;
    while (y) {
        if (y & 1) res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}

Complex qpow(Complex x, ll y) {
    Complex res = {1, 0};
    while (y) {
        if (y & 1) res = res * x;
        x = x * x;
        y >>= 1;
    }
    return res;
}

bool legendre(ll x) {
    return qpow(x, (mod - 1) >> 1) == 1;
}

ll cipolla(ll n, ll p) {
    n %= p, mod = p;
    if (!n) return 0;
    if (!legendre(n)) return -1;
    ll a = rand() % mod;
    while (legendre((a * a + mod - n) % mod)) a = rand() % mod;
    I_mul_I = (a * a + mod - n) % mod;
    return qpow(Complex({a, 1}), (mod + 1) >> 1).a;
}

int main() {
    srand(time(0));
    int T;
    scanf("%d", &T);
    while (T -- ) {
        ll x, p;
        scanf("%lld%lld", &x, &p);
        ll ans = cipolla(x, p);
        if (ans == -1) puts("Hola!");
        else if (ans == 0) puts("0");
        else {
            if (ans > p - ans) ans = p - ans;
            printf("%lld %lld\n", ans, p - ans);
        }
    }
    return 0;
}