引言

我们在研究多项式开根的时候，想到了一个问题，若常数项不为 1，那么怎么开根呢？
这就涉及到二次剩余。
那么什么是二次剩余呢？若在模 $p$意义下，存在一个 $x$，使得 $x^2 \equiv a \pmod{p}$，则称 $a$为 $x$关于 $a$的二次剩余。若不存在这样的 $x$，则称 $a$为非二次剩余。
现在我们知道了 $a$，要求解 $x$，怎么办呢？

p 为奇素数

首先引入欧拉准则：
当 $a$为模 $p$意义下的二次剩余时，$a^{\frac{p-1}{2}} \equiv 1 \pmod{p}$
当 $a$为模 $p$意义下的非二次剩余时，$a^{\frac{p-1}{2}} \equiv p-1 \pmod{p}$
我们要求的 $x$满足：$(a^{-1}x^2)^{2^0} \equiv 1 \pmod{p}$
设 $p-1=s2^t$，设 $x _ {t-1}=a^{\frac{s+1}{2}}$，那么根据欧拉准则第一条，有：$(a^{-1}x_{t-1}^2)^{2^{t-1}} \equiv 1 \pmod{p}$
诶…… 要不我们设 $(a^{-1}x _ {t-k}^2)^{2^{t-k}} \equiv 1 \pmod{p}$，这样我们要求的就是 $x_0$
思考如何从 $x _ {t-k}$推到 $x _ {t-k-1}$。
设 $e _ {t-k}=a^{-1}x _ {t-k}^2$
若 $e _ {t-k}^{2^{t-k-1}} \equiv 1 \pmod{p}$（即将 $e _ {t-k}^{2^{t-k}}$开根），显然 $x _ {t-k-1}=x _ {t-k}$
若 $e _ {t-k}^{2^{t-k-1}} \equiv p-1 \pmod{p}$。我们试图让 $x _ {t-k}$乘一个值使得它变成 $x _ {t-k-1}$。那么想到欧拉准则的第二条，首先随机一个非二次剩余 $b$，然后发现 $(b^{2^{k-1}s})^{2^{t-k}} \equiv p-1 \pmod{p}$，所以 $b^{2^{k-1}s}$是我们满足条件的值，此时让 $x _ {t-k-1}=b^{2^{k-1}s}x _ {t-k}$即可。
最后 $x_0$其实有正负两个解，都满足条件。
例题:URAL 1132
代码:

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
int T,a,p,bin[22];
int ksm(int x,int y,int p) {
    int re=1;
    for(;y;y>>=1,x=1LL*x*x%p) if(y&1) re=1LL*re*x%p;
    return re;
}
int jud(int x,int p) {return ksm(x,(p-1)/2,p)==1;}
void work() {
    int s=p-1,b,t=0;
    while(!(s&1)) ++t,s>>=1;
    int inva=ksm(a,p-2,p),e=ksm(a,s,p),x=ksm(a,(s+1)/2,p);
    while("xzy is too strong") {
        b=rand()%p+1,b=((b*b-a)%p+p)%p;
        if(b&&!jud(b,p)) break;
    }
    for(RI k=1;k<t;++k)
        if(ksm(e,bin[t-k-1],p)!=1)
            x=1LL*x*ksm(b,bin[k-1]*s,p)%p,e=1LL*inva*x%p*x%p;
    int x1=x,x2=p-x;
    if(x1>x2) swap(x1,x2);
    printf("%d %d\n",x1,x2);
}
int main()
{
    srand(19260817);
    T=read();
    bin[0]=1;for(RI i=1;i<=20;++i) bin[i]=bin[i-1]<<1;
    while(T--) {
        a=read(),p=read();
        if(p==2) {puts("1");continue;}
        if(!jud(a,p)) {puts("No root");continue;}
        work();
    }
    return 0;
}

p 为奇素数的幂

求满足 $x^2 \equiv a \pmod{p^q}$的 $x$。
设 $a=p^kd$。
显然答案是 $x=p^{\frac{k}{2}}x_0$的形式。
则 $p^k x _ 0^2 \equiv p^k d \pmod{p^q}$，也就是说 $(d-x _ 0^2)p^k \equiv 0 \pmod{p^q}$，那么有 $(d-x _ 0^2) \equiv 0 \pmod{p^{q-k}}$
问题转化为求 $x _ 0^2 \equiv d \pmod{p^{q-k}}$，而 $d$与 $p$是互质的。
为了方便起见，假设我们现在要求解的问题是 $x^2 \equiv a \pmod{p^q}$，$a$与 $p$互质。

找到一个模 $p^q$的简化剩余系下的原根 $g$，我们就可以用 $g^r(1 \leq r \leq \phi(p^q))$来表示所有在模 $p^q$意义下与 $p^q$互质的数。
当 $r$为奇数时，设存在 $g^r \equiv g^{2m} \pmod{p^q}$。也就是 $r \equiv 2m \pmod{\phi(p^q)}$，也就是 $r=2m+k\phi(p^q)$。
我们知道 $\phi(p^q)=(p-1)p^{q-1}$，又因为 $p$是奇素数，所以 $\phi(p^q)$是偶数，所以 $2m+k\phi(p^q)$也是偶数。而 $r$是奇数，所以显然找不到这样的 $m$。
当然因为 $g$肯定是与 $p$互质的，所以 $g^r \equiv g^{2m}p^t \pmod{p^q}$也是不可能成立的啦。所以此时 $g^r$是个二次非剩余啦。
而当 $r$为偶数的时候，显然 $g^r$是个二次剩余啦。

对于任意二次剩余 $g^{2k}$，有
$$(g^{2k})^{\frac{\phi(p^q)}{2}} = (g^k)^{\phi(p^q)} \equiv 1 \pmod{p^q}$$
对于任意二次非剩余 $g^{2k+1}$有：
$$(g^{2k+1})^{\frac{\phi(p^q)}{2}} \equiv g^{\frac{\phi(p^q)}{2}} \pmod(p^q)$$
我们知道 $g^{\frac{\phi(p^q)}{2}}$与 $g^{\phi(p^q)}$肯定不相等，而后者等于 1, 前者是后者的开根，所以等于-1。
我们得到了一个 new 欧拉准则。
求解时，先将问题转化为 $a$与 $p$互质，然后令 $\phi(p^q)=s2^t$，套用 p 为奇素数时的求解方法即可。

p 为 2 的幂

这个嘛…… 同样，化一下，令 $a=2^kd$，那么求解 $x _ 0^2 \equiv d \pmod{2^{q-k}}$，然后解就是 $x=2^{\frac{k}{2}}(x _ 0+2^{q-k}t)$的形式。
然后我们知道，当 $q=1$的时候，当 $a=1$时有解 $x=1$
当 $q=2$时，当 $a=1$时有解 $x=1,x=3$
当 $q=3$时，当 $a=1$时有解 $x=1,x=3,x=5,x=7$
我们将 $q=k$意义下解的形式写成 $x _ k= \pm (y _ k+t _ k 2^{k-1})$。记 $a_k = a \bmod{2^k}$
继续推，现在我们已知了 $x _ {k-1}\equiv\pm(y _ {k-1}+t _ {k-1}2^{k-2}) \pmod{2^{k-1}}$
那么 $x _ {k-1}^2$在模 $2^k$意义下可能是 $a _ {k-1}$或 $a _ {k-1}+2^{k-1}$。我们在现在符合条件的若干 $t _ {k-1}$值中选择出能使 $x _ {k-1}^2 \equiv a _ k \pmod{2^k}$的，然后：
$$(y _ {k-1}+t _ {k-1}2^{k-2})^2 \equiv a _ k \pmod{2^k}$$
将左边的式子拆开，得到 $y _ {k-1}^2 + t _ {k-1}2^{k-1}y _ {k-1}+t _ {k-1}^2 2^{2k-4}$，由于我们之前已经保证过了 $a$是奇数，所以 $y$一定是奇数，而我们知道 $t_{k-1}2^{k-1} \times 2 \equiv 0 \pmod{2^k}$所以第二项一定等于 $t_{k-1}2^{k-1}$。第三项则一定等于 0。
所以
$$y _ {k-1}^2 + t _ {k-1}2^{k-1} \equiv a _ k \pmod{2^k}$$
$$t _ {k-1}2^{k-1} \equiv a _ k -y _ {k-1}^2 \pmod{2^k}$$
$$t _ {k-1} \equiv \frac{a _ {k} – y _ {k-1}^2}{2^{k-1}} \pmod{2}$$
所以设 $t _ {k-1}= \frac{a _ {k} – y _ {k-1}^2}{2^{k-1}} + 2 t _ k$，那么
$$x _ k = \pm (y _ {k-1}+\frac{a _ k- y _ {k-1}^2}{2} + 2^{k-1}t _ k)$$
也就是说，$y _ k=y _ {k-1}+\frac{a _ k- y _ {k-1}^2}{2}$
所以我们就从 $q=3$开始不断往上推，就可以出解了。

p 为合数

嗯，将 p 质因数分解，然后分别求解，中国剩余定理合并即可。