VI.【模板】多项式开根(加强版)
这题和上题唯一的区别就是\(a_0\)的取值——本题\(a_0\)不一定为\(1\)。
咋办呢?
我们观察到里面有一句话:
保证\(a_0\)是\(\bmod\ 998244353\)下的二次剩余。
二次剩余?这是啥?能吃吗?
这时,你突然想起曾经看到过一道模板题:
于是你兴奋地点了进去,发现这正是我们需要的:求\(x^2\equiv n\pmod{p}\)的根。
于是我们先讲解一下二次剩余的Cipolla算法。该算法仅应用于\(p\)是奇质数的情形。
- 在上述方程中,\(x\)有多少解?
我们先从简单的情形想起——假设它有两解\(x_1,x_2\),则一定有
于是
显然\(x_1-x_2\not\equiv0\),不然就是重根了。
则必有\(x_1+x_2\equiv 0\),即\(x_1\)与\(x_2\)是在模\(p\)意义下的相反数。
显然一个数只有唯一的相反数,故实际上二次剩余方程如果有解,则一定有两解。
(实际上\(n\equiv0\)是一个特例——它只有一根\(x=0\),于是可以特判掉,因此我们接下来讨论的\(n\)都是非\(0\)的)
- 怎样判断对于一个\(n\),其二次剩余方程是否有解?
如果一个\(n\)关于\(p\)的二次剩余方程有解,则我们称\(n\)是\(p\)的二次剩余。同理,如果无解,我们称其为\(p\)的非二次剩余。
我们从费马小定理开始:
因为我们Cipolla算法应用的前提是\(p\)是奇质数,所以\(\varphi(p)=p-1\),所以
显然\(p-1\)是偶数,于是我们两边开根,得到
我们考虑当\(n\)是二次剩余时,必有
因此\(n^{\frac{p-1}{2}}\equiv1\pmod p\)是\(n\)是二次剩余的必要条件。
我们考虑再证其充分性。设\(n\equiv g^k\pmod p\),其中\(g\)是\(p\)的原根。则必有\((g^k)^{\frac{p-1}{2}}\equiv 1\pmod p\)。
而又有\(g^{\varphi(p)}\equiv 1\pmod p\),故
所以
则\(k\)必须是一个偶数来消掉分母上的\(2\)。于是我们只要令\(x\equiv g^{\frac{k}{2}}\)即是二次剩余方程的一个根,故\(n\)是二次剩余。
因此\(n^{\frac{p-1}{2}}\equiv1\pmod p\)是\(n\)是二次剩余的充分条件。
综上,\(n^{\frac{p-1}{2}}\equiv1\pmod p\),等价于\(n\)是\(p\)的二次剩余。
- 如何求根(Cipolla算法)
我们考虑随机出来一个\(a\)使得\(a^2-n\)不是二次剩余。这期望需要两次随机,因为每组相反数都对应着一组二次剩余,一共\(\dfrac{p-1}{2}\)组相反数,故一共有\(\dfrac{p-1}{2}\)个二次剩余,则剩下的数都不是二次剩余,故期望两次即可随机得到一个非二次剩余。
我们现在设一个\(i^2\equiv a^2-n\pmod p\)。
等等,\(a^2-n\)不是非二次剩余吗?那咋出来一个\(i^2\)呢?
类比虚数概念,这个\(i\)实际上也是一个虚数,它没有实际对应的数。
我们要证明几条引理:
- \(i^p\equiv -i\pmod p\)。
因为\(a^2-n\)是非二次剩余,所以\((a^2-n)^{\frac{p-1}{2}}\equiv-1\),
所以
- \((A+B)^p\equiv A^p+B^p\pmod p\)
我们二项式展开后,除了\(\dbinom{p}{0}\)与\(\dbinom{p}{p}\)两项不存在\(p\)以外,其它项全都存在因子\(p\),因此其\(\equiv0\pmod p\),可以忽略,因此只保留\(A^p,B^p\)两项。
于是
所以我们直接计算复数\(a+i\)的\(p+1\)次幂即可得到一个解,取相反数即可得到令一个解。
注意这里\(i^2\)的取值应是\(a^2-n\),而不是正常复数中的\(-1\)!
时间复杂度期望为\(O(\log p)\)。
代码(【模板】二次剩余):
#include<bits/stdc++.h>
using namespace std;
int T,n,p,sqri;
struct cp{
int x,y;
cp(int a=0,int b=0){x=a,y=b;}
friend cp operator *(const cp &a,const cp &b){
return cp((1ll*a.x*b.x%p+1ll*a.y*b.y%p*sqri%p)%p,(1ll*a.y*b.x%p+1ll*a.x*b.y%p)%p);
}
};
int ksm(int x,int y){
int z=1;
for(;y;y>>=1,x=1ll*x*x%p)if(y&1)z=1ll*z*x%p;
return z;
}
cp ksm(cp x,int y){
cp z=cp(1,0);
for(;y;y>>=1,x=x*x)if(y&1)z=z*x;
return z;
}
bool che(int x){
return ksm(x,p>>1)==1;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&p),n%=p;
if(!n){puts("0");continue;}
if(!che(n)){puts("Hola!");continue;}
int a=rand()%p;
while(true){
sqri=(1ll*a*a%p-n+p)%p;
if(!a||che(sqri))a=rand()%p;
else break;
}
cp tmp=cp(a,1);
tmp=ksm(tmp,(p+1)>>1);
int u=tmp.x,v=(p-tmp.x)%p;
if(u>v)swap(u,v);
printf("%d %d\n",u,v);
}
return 0;
}
然后本题就只需要把迭代的初始值改成用Cipolla求出的二次剩余方程的根即可。
时间复杂度\(O(n\log n)\),代码就不贴了。