class="markdown_views prism-atelier-sulphurpool-light">

引言

我们在研究多项式开根的时候，想到了一个问题，若常数项不为1，那么怎么开根呢？
这就涉及到二次剩余。
那么什么是二次剩余呢？若在模$p$意义下，存在一个$x$，使得$x^2 equiv a pmod{p}$，则称$a$为$x$关于$p$的二次剩余。若不存在这样的$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 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; }