原根和多项式学习笔记
1. 阶
1.1. 定义
假设模数 m 和底数 a 互质。
对于 \(n\in Z\)，\(a^n \bmod m\) 呈循环结构，这种循环节的最小长度就是 a 模 m 的阶。
准确来说，对于 \(a\bot m\)，满足同余式 \(a^n\equiv 1(\bmod m)\) 的最小正整数 n 称作 a 模 m 的阶，记作 \(\delta_m(a)\)。
1.2. 幂的循环结构
利用阶，就可以刻画幂的循环结构，对于 \(a^n\bmod m\)，记 \(n=k\delta_m(a)+r\),则 \(a^n\equiv a^r(\bmod m)\)。
性质1：对于 \(a\in Z,m\in N+,a\bot m\)，\(a^0,a^1,\dots a^{\delta_m(a)-1}\) 模 m 余数互不相同。
性质2：对于 \(a,n\in Z,m\in N+,a\bot m\)，\(a^n\equiv 1(\bmod m)\) 成立当且仅当 \(n|\delta_m(a)\)
根据欧拉定理 \(a^{\varphi(m)}\equiv 1(\bmod m)\)，所以对于所有 \(a\bot m\)，必有 \(\delta_m(a)|\varphi(m)\)，即 \(\varphi(m)\) 是所有 \(a\bot m\) 的阶的公倍数。
性质3：对于 \(a,k\in Z,m\in N+,a\bot m\)，有 \(\delta_m(a^k)=\dfrac{\delta_m(a)}{gcd(\delta_m(a),k)}\)
1.3. 乘积的阶
设 a,b 是与 m 互质的不同整数，已知阶 \(\delta_m(a)\) 和 \(\delta_m(b)\)，那么可以得到：
性质4：
\(\dfrac{[\delta_m(a),\delta_m(b)]}{(\delta_m(a),\delta_m(b))}|\delta_m(ab)|[\delta_m(a),\delta_m(b)]\)
后半部分根据性质2易得，考虑前半段：
因为 \(1\equiv (ab)^{\delta_m(ab)\delta_m(b)}\equiv a^{\delta_m(ab)\delta_m(b)}(\bmod m)\)，所以
\(\delta_m(a)|\delta_m(ab)\delta_m(b)\)
两侧消去 \((\delta_m(a),\delta_m(b))\)，去掉互质部分，得到
同理，
因为左侧互质，所以就是之前的结论了。
同时 \(\delta_m(ab)=\delta_m(a)\delta_m(b)\Leftrightarrow \delta_m(a)\bot \delta_m(b)\)
性质5：对于 \(a,b\in Z,m\in N+,a,b\bot m\)，存在 \(c\in Z\) 且 \(c\bot m\) 使得：\(\delta_m(c)=[\delta_m(a),\delta_m(b)]\)
设 \(\delta_m(a)=\prod_p p^{a_p},\delta_m(b)=\prod_p p^{b_p}\)
根据 \(a_p\) 和 \(b_p\) 的大小关系分成两类：
所以：\(\delta_m(a)=xAyA,\delta_m(b)=xByB\)
因为 \(xA\bot xB\)
所以：\(\delta_m(a^{yA}b_{yB})=xAxB=[\delta_m(a),\delta_m(b)]\)
2. 原根
2.1. 定义
对于 \(m\in N+\) ，如果存在 \(g\in Z,g\bot m\) 使得 \(\delta_m(g)=\varphi(m)\) 则 g 为 m 的原根。
但是并非所有整数 m 都存在原根，若存在，必然满足 \(g,g^2,\dots,g^{\varphi(m)}\) 所在同余类互不相同，特别地，对于素数 p，余数 \(g^i\bmod p\) 对于
\(i=1,2,\cdots,p-1\) 两两不同。
2.2. 原根判定定理
已知模数 \(\varphi(m)\) 的的所有质因子，易判断是否存在。
定理：对于整数 \(m>3\) 和 \(g\bot m\) 那么 g 是 模 m 的原根当且仅当对于 \(\varphi(m)\) 的每个质因数 \(p\)，都有 \(g^{\frac{\varphi(m)}{p}}\neq 1(\bmod m)\)
2.3. 原根个数
模 \(m\) 的原根个数为 \(\varphi(\varphi(m))\)。
证明：
设 m 有原根 g。
所以只有满足 \((\varphi(m),k)=1\) 时，才有原根。
2.4. 原根存在定理
模 m 的原根存在，当且仅当 \(m=1,2,4,p^c,2p^c\)，p 是奇素数。
当 \(m=1,2,4\) 时，\(g=0,1,3\)。
其他的在 wiki,不证了。
2.5. 原根求法
可以直接枚举每个数，然后 \(log^2\) check。
也可以随机，因为原根密度较高，期望复杂度 \(O((\log^2 m) \log \log m)\)。
还有就是另一个瓶颈在于 \(\varphi(m)\) 的质因数分解。
2.6. 例题
P6091 【模板】原根
按照上述做法直接跑就行了。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=1e6;
int T,n,d;
int p[M+5],phi[M+5],lst[M+5],cnt;
bool vis[M+5];
void init()
{
phi[1]=1;
for(int i=2;i<=M;i++)
{
if(!vis[i]) p[++cnt]=i,phi[i]=i-1,lst[i]=i;
for(int j=1;i*p[j]<=M;j++)
{
vis[i*p[j]]=1,lst[i*p[j]]=p[j];
if(i%p[j]) phi[i*p[j]]=phi[i]*(p[j]-1);
else
{
phi[i*p[j]]=phi[i]*p[j];
break;
}
}
}
}
bool check(int x)
{
if(x==2||x==4) return 1;
int cnt=0,fl=0,v=0;
while(x>1)
{
if(lst[x]==2) cnt++;
else
{
if(v&&v!=lst[x]) fl=1;
else v=lst[x];
}
x=x/lst[x];
}
if(cnt<=1&&!fl) return 1;
return 0;
}
ll qpow(ll x,int y,int p)
{
ll res=1;
while(y)
{
if(y&1) res=res*x%p;
x=x*x%p;
y>>=1;
}
return res;
}
bool check(int x,int y)
{
if(qpow(x,y,n)!=1) return 0;
int v=y;
// printf("%d %d\n",x,y);
while(y>1)
{
if(qpow(x,v/lst[y],n)==1) return 0;
y/=lst[y];
}
return 1;
}
int gcd(int a,int b)
{
if(b==0) return a;
return gcd(b,a%b);
}
int ans[M+5];
int main()
{
srand((unsigned)time(0));
init();
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&d);
if(!check(n))
{
printf("0\n\n");
continue;
}
printf("%d\n",phi[phi[n]]);
int x=0,sum=0,val=1;
while(1)
{
x=1ll*rand()*rand()%(n-1)+1;
if(check(x,phi[n])) break;
}
ans[++sum]=x,val=x;
for(int i=2;i<phi[n];i++)
{
val=1ll*val*x%n;
if(gcd(i,phi[n])!=1) continue;
ans[++sum]=val;
}
// printf("%d ",sum);
sort(ans+1,ans+sum+1);
for(int i=d;i<=sum;i+=d) printf("%d ",ans[i]);
printf("\n");
}
return 0;
}
bzoj 1420. Discrete Root
首先 p 是质数，所以必然有原根且这些次幂覆盖了 1 到 p-1 的所有值。
找到一个 p 的原根 g，那么 \(g^k\) 必然是 p 的原根，所以必然存在 \((g^k)^x\equiv a(\bmod p)\)
交换一下， \((g^x)^k\equiv a(\bmod p)\)，\(g^x\) 就是解，x 可以 bsgs
BZOJ2219 数论之神
首先模数一定是奇数，但是问题在于它不一定是质数，所以难以像上一个题一样直接做。
考虑拆分这个数，它一定会被分成若干个奇质数的幂次的相乘形式，对每个部分就可以处理了。
但是为什么能拆成这些部分？因为模数互质，考虑 CRT
首先，如果 \(p^k|b\) 那么要保证左边的 p 的次幂超过 k 就可以。
否则就是可以分成两部分，一个是 p 的幂次部分，这个可以直接算出来，然后同时除掉。
这样 b 和 mod 就互质了，然后可以按照上面的做法，先求原根，记为 g，设 \(b=g^t,x=g^s\) 然后就是同余方程的解数。
3. FFT
3.1. 多项式
数学定义中，多项式就是若干单项式之和，但是可以发现不同单项式的区别在于系数和次数。
所以这里有一个系数表示法，就是依次把系数写下来，就能得到一个向量。
所以就有暴力的乘法方法，每次依次将两个单项式对应相乘 \(O(n^2)\)。
引理：一个 n 次多项式可以通过 n+1 个点来确定。
因为根据平常解方程的原理，一共 n+1 个未知数，所以需要 n+1 个不同的方程，当一维坐标确定时，就可以只用一个数组存储。
这东西叫点值表示法，这样乘的时候只需要把对应位置的值相乘就行了，但是转化的过程是 \(O(n^2)\) 的。
3.2. 复数
在实数域内，根号下必须是非负数，因为 \(a^2\ge 0\)
但是有一个东西 \(i\) 满足 \(i^2=-1\)，就是虚数单位，没有现实意义。
形如 \(bi\) 形式的数称为纯虚数，形如 \(a+bi\) 的形式的数称为复数，\(a\) 是实部，\(b\) 是虚部。
然后就能得到复数域，复数可以作为方程的解，所以一个 n 次方程有且仅有 n 个根。
运算上，就是利用乘法分配律化成 \(a+bi\) 的形式。
除法拿出来说一下，因为这东西和根号一样，可以利用平方差公式把分母化成一个数，所以要同乘共轭复数化简。
\(\frac{z_1}{z_2}=\frac{a_1a_2+b_1b_2}{a_2^2+b_2^2}+\frac{a_2b_1-a_1b_2}{a_2^2+b_2^2}\)
同时复数也具有几何意义，但是它是由 a,b 两部分组成的，所以要用到坐标系，就是复平面。
欧拉公式：\(e^{i\theta}=cos(\theta)+isin(\theta)\)
3.3. 单位根
考虑这样的一个方程，\(w^n=1\)，根据上面的结论，一共有 n 个根，而这 n 个根叫做 n 次单位根，记作 \(w_n\)
将这些点画在复平面上，就形成了一个半径为 1 的圆，就是单位圆，并且可以发现是圆上的 n 等分点。
根据欧拉公式，可以直接求出单位根，\(w_n=e^{\frac{2i\pi}{n}}=cos(\frac{2\pi}{n})+isin(\frac{2\pi}{n})\)
其他的就是上面这个值的若干次方，有一个定理 \(w_n^k=w_{dn}^{dk}\)，就是消去定理。
当 n 为偶数时，根据消去定理，\(w_n^{\frac{n}{2}}=w_2=-1\)
进一步得到 \(w_n^{\frac{n}{2}+m}=w_n^{\frac{n}{2}}*w_n^m=-w_n^m\)
折半定理：对于偶数 n，n 次单位根的平方构成的集合就是 \(\frac{n}{2}\) 次单位根的集合。
\((w_n^m)^2=(w_n^{\frac{n}{2})+m})^2\)
求和引理：对于正整数 n,k，满足 n 不为 k 因数，\(\sum_{i=0}^{n-1} (w_n^k)^i=0\)
3.4. 多项式转换的优化
首先一定要得到的就是第一个点的坐标，考虑能不能通过优化选点减少计算量。
首先可以发现如果是所有单项式都是偶数或奇数次幂，那么一定可以通过选相反数的方法减少运算。
如果是普通多项式，考虑拆解，这里我们默认 n 是偶数，否则补一个系数为 0 的项。
\(f1(x)=a_1x^0+a_3x^1+\dots,f2(x)=a_0x^0+a_2x^1+\dots\)
然后能得到 \(f(x)=xf1(x^2)+f2(x^2)\)
就出现问题了，没有实数的平方是负数，所以没办法继续递归。
3.5. 快速傅里叶变换
要求平方后还有负数出现，那么必须用到复数，而复数中单位根有比较好的性质。
我们就把上面的 x 带成单位根，得到:
\(f(w_n^m)=w_n^mf1((w_n^m)^2)+f2((w_n^m)^2)=w_n^mf1(w_{\frac{n}{2}}^m)+f2(w_{\frac{n}{2}}^m)\)
再带一下 \(w_n^{m+\frac{n}{2}}\)，得到 \(f(w_n^{m+\frac{n}{2}})=w_n^mf1(w_{\frac{n}{2}}^m)-f2(w_{\frac{n}{2}}^m)\)
所以求出 \(f1(w_{\frac{n}{2}}^m)\) 和 \(f2(w_{\frac{n}{2}}^m)\) 就能解出来。
然后就是一个分治了，这样就实现了式子->点值，时间复杂度 \(O(n\log n)\)。
现在的问题是如何转回系数表示法，最简单的方法是拉插，\(O(n^2)\)
但是显然是不行的，把这个过程其实可以理解成矩阵乘法，此时我们需要乘一个逆矩阵得到原来的值。
因为矩阵里的东西都是复数，他们的倒数就是共轭复数，所以可以再做一遍 FFT。
3.6. 例题
【模板】多项式乘法（FFT）
题如其名，板子，按上面的直接做
#include<cstdio>
#include<cmath>
using namespace std;
const int N=3e6+5;
const double pi=3.1415926535897932384626433;
int n,m,len;
struct cplx{
double re,imp;
cplx operator +(const cplx &x)const{
return (cplx){re+x.re,imp+x.imp};
}
cplx operator -(const cplx &x)const{
return (cplx){re-x.re,imp-x.imp};
}
cplx operator *(const cplx &x)const{
return (cplx){re*x.re-imp*x.imp,re*x.imp+imp*x.re};
}
}a[N],b[N],c[N];
void FFT(cplx *a,int n,int opt)
{
if(n==1) return;
int m=(n>>1);
cplx p1[m],p2[m];
for(int i=0;i<m;i++) p1[i]=a[i*2],p2[i]=a[i*2+1];
FFT(p1,m,opt),FFT(p2,m,opt);
cplx w=(cplx){cos(2.0*pi/n),opt*sin(2.0*pi/n)},wk=(cplx){1,0};
for(int i=0;i<m;i++,wk=wk*w)
{
a[i]=p1[i]+wk*p2[i];
a[i+m]=p1[i]-wk*p2[i];
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++)
{
scanf("%lf",&a[i].re);
}
for(int i=0;i<=m;i++)
{
scanf("%lf",&b[i].re);
}
len=1;
while(len<=n+m) len<<=1;
// printf("%d ",len);
FFT(a,len,1),FFT(b,len,1);
for(int i=0;i<len;i++)
{
// printf("%lf %lf %lf %lf\n",a[i].re,a[i].imp,b[i].re,b[i].imp);
c[i]=a[i]*b[i];
}
FFT(c,len,-1);
for(int i=0;i<=n+m;i++)
{
printf("%d ",(int)(c[i].re/len+0.5));
}
return 0;
}
Normal
考虑什么情况下 i 会对 j 产生贡献，必然在 j 被选中的时候 i,j 处在同一个连通块内。
方案数就是 \(\frac{dis(i,j)!}{(dis(i,j)+1)!}=\frac{1}{(dis(i,j)+1)!}\)，所以就是要求每个距离的点对数。
考虑点分治，显然可以先求出根到每个点的 dis，然后进行合并，但是合并的过程是 \(n^2\) 的。
观察这东西的形式，可以发现 \(cnt_a\) 和 \(cnt_b\) 会贡献到 a+b，很像多项式乘法的形式，所以 FFT 卷积即可。
Triple
如果是考虑顺序的完全背包，那么显然可以用 FFT 直接做。
难点在于不能重复选，考虑容斥，如果只选两个，那么不重复就是两种选法，重复的就是一个选两遍，对应减掉。
考虑 3 个的，全选成一样的可以直接判掉，两个一样的考虑打包再和单个的卷一遍，一共 3 种情况，乘上然后对应相减。
剩下的每个对应 6 种顺序，除掉之后和选 1-2 个的求和。
万径人踪灭
先枚举回文中心，然后合法的就是在两边相同的对里面任选，不连续这个要求二分 +hash 找回文串长度。
难点在于有多少对满足相等，可以发现因为同一个中心下标和固定。
所以可以把 ab 分开，然后标记出现位置为 1，其余为 0，这样只有乘积为 1 才相等，卷一下就可以了。
4. NTT
因为一道题拿 FFT 死活过不去，发现 NTT 可以处理模数，所以学习。
4.1. 原根
FFT 有一个很难受的问题，就是单位根的精度，以及这东西没办法取模
定义和求法在上面，考虑在做 FFT 的时候用到了哪些性质，记 p 的一个原根为 g。
首先 \(w_n^n=1\) 那么 \((g^r)^n=1\) 所以 \(r=\frac{\varphi(p)}{n}\)
我们让 \(g^r\) 作为新的单位根，考虑是否满足性质。
\(w_n^k=g^{\frac{(p-1)k}{n}}=g^{\frac{2(p-1)k}{2n}}=w_{2n}^{2k}\)
因为 \(g^{p-1}\neq g^{\frac{p-1}{2}},(g^{\frac{p-1}{2}})^2\equiv 1(\bmod p)\)
所以 \(g^{\frac{p-1}{2}}\equiv -1(\bmod p)\)
所以 \(w_{2n}^{k}\equiv -w_{2n}^{n+k}(\bmod p)\)
4.2. 例题
[SDOI2015] 序列统计
可以想到一个 \(O(m^2\log)\) 的做法，类似于快速幂，每次长度翻倍，枚举两边的乘积，暴力计算。
但是因为是相乘关系难以按正常的方法维护，考虑到若 \(a=c^s,b=c^t,ab=c^{s+t}\)
考虑取一个底数，然后弄出每个数的指数，因为要求取遍每个数，底数可以选原根。
这样就是一个加的形式，因为带取模，必须用 NTT。
#include<bits/stdc++.h>
#define ll long long
#define double long double
using namespace std;
const int N=8005,mod=1004535809,g1=3,invg=334845270;
ll c[N*3],d[N*3];
int n,m,r,siz,a[N],pw[N],p[N];
ll sum[N],ans[N];
ll qpow(ll x,int y,int mod)
{
ll res=1;
while(y)
{
if(y&1) res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
bool check(int x)
{
if(qpow(x,m-1,m)!=1) return 0;
int y=m-1;
for(int i=2;i*i<=y;i++)
{
if(y%i==0)
{
if(qpow(x,(m-1)/i,m)==1) return 0;
while(y%i==0) y/=i;
}
}
if(y!=1)
{
if(qpow(x,(m-1)/y,m)==1) return 0;
}
return 1;
}
void NTT(ll *a,int n,int opt)
{
if(n==1) return;
int m=n/2;
ll p1[m],p2[m];
for(int i=0;i<m;i++) p1[i]=a[i*2],p2[i]=a[i*2+1];
NTT(p1,m,opt),NTT(p2,m,opt);
ll wk=1,w=qpow(opt==1?g1:invg,(mod-1)/n,mod);
for(int i=0;i<m;i++,wk=wk*w%mod)
{
a[i]=(p1[i]+wk*p2[i])%mod;
a[i+m]=(p1[i]+mod-wk*p2[i])%mod;
}
}
void solve(ll *a,ll *b)
{
for(int i=1;i<m;i++)
{
c[i]=a[pw[i]],d[i]=b[pw[i]];
}
int len=1,l=0;
while(len<=2*m) len*=2,l++;
NTT(c,len,1),NTT(d,len,1);
for(int i=0;i<len;i++) c[i]=c[i]*d[i]%mod;
NTT(c,len,-1);
for(int i=0;i<m;i++) b[i]=0;
int inv=qpow(len,mod-2,mod);
for(int i=1;i<len;i++)
{
int x=(i-1)%(m-1)+1;
b[pw[x]]=(c[i]*inv+b[pw[x]])%mod;
// printf("%d ",c[i]*inv%mod);
}
// printf("\n");
for(int i=0;i<len;i++) c[i]=d[i]=0;
}
int main()
{
srand((unsigned)time(0));
scanf("%d%d%d%d",&n,&m,&r,&siz);
for(int i=1;i<=siz;i++)
{
scanf("%d",&a[i]);
if(a[i]==0) i--,siz--;
}
int g=0;
while(1)
{
g=1ll*rand()*rand()%(m-1)+1;
if(check(g)) break;
}
// printf("%d ",g);
int v=1;
for(int i=1;i<=m-1;i++)
{
v=v*g%m;
pw[i]=v,p[v]=i;
// printf("%d ",pw[i]);
}
ans[1]=1;
for(int i=1;i<=siz;i++) sum[a[i]]=1;
while(n)
{
if(n&1) solve(sum,ans);
solve(sum,sum);
n>>=1;
}
printf("%lld",(ans[r]+mod)%mod);
return 0;
}
【模板】任意模数多项式乘法
这东西一是 \(\varphi(p)\) 不一定是 \(a2^k+1\)，二是不一定有逆元。
考虑构造一组模数，求出对他们取模的结果，然后 CRT 确定唯一的值。
大概要取 3 个数，数的上界为 \(nV^2=10^{23}\)，要求乘积大于上界，满足是 \(a2^k+1\)，做3 遍 NTT。
注意常数！
点击查看代码
#include<cstdio>
#define ll long long
const int mod1=998244353,mod2=1004535809,mod3=469762049,g=3;
const int N=3e5+5;
using namespace std;
int n,m,p;
ll f1[N],f2[N],c1[N],c2[N],c3[N],v1[50],v2[50];
int d[N],a[N],b[N];
ll qpow(ll x,int y,int mod)
{
ll res=1;
while(y)
{
if(y&1) res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
ll mul(ll a,ll b,ll p)
{
ll res=0;
while(b)
{
if(b&1) res=(res+a)%p;
a=(a+a)%p;
b>>=1;
}
return res;
}
inline void NTT(int *a,int n,int opt,int mod,int t)
{
if(n==1) return;
int m=n/2;
int p1[m],p2[m];
for(int i=0;i<m;i++) p1[i]=a[i*2],p2[i]=a[i*2+1];
NTT(p1,m,opt,mod,t+1),NTT(p2,m,opt,mod,t+1);
ll w=(opt==1?v1[t]:v2[t]),wk=1;
for(int i=0;i<m;i++,wk=wk*w%mod)
{
a[i]=(p1[i]+wk*p2[i])%mod;
a[i+m]=(p1[i]-wk*p2[i])%mod;
}
}
int len=1;
inline void solve(ll *c,int mod)
{
for(int i=0;i<len;i++) a[i]=f1[i],b[i]=f2[i];
int x=len;
for(int i=1;i<=20&&x;i++)
{
v1[i]=qpow(g,(mod-1)/x,mod);
v2[i]=qpow(qpow(g,mod-2,mod),(mod-1)/x,mod);
x/=2;
}
NTT(a,len,1,mod,1),NTT(b,len,1,mod,1);
for(int i=0;i<len;i++) d[i]=1ll*a[i]*b[i]%mod;
NTT(d,len,-1,mod,1);
ll inv=qpow(len,mod-2,mod);
for(int i=0;i<len;i++)
{
c[i]=(d[i]*inv%mod+mod)%mod;
// printf("%lld ",c[i]);
}
// printf("\n");
}
inline int read()
{
int x=0;
char ch=getchar();
while(ch<48||ch>57) ch=getchar();
while(ch>=48&&ch<=57) x=x*10+ch-48,ch=getchar();
return x;
}
int main()
{
n=read(),m=read(),p=read();
for(int i=0;i<=n;i++)
{
f1[i]=read();
}
for(int i=0;i<=m;i++)
{
f2[i]=read();
}
while(len<=n+m) len=len*2;
solve(c1,mod1),solve(c2,mod2),solve(c3,mod3);
ll m1=1ll*mod1*mod2;
for(int i=0;i<=n+m;i++)
{
ll t=mul(c1[i]*mod2%m1,qpow(mod2%mod1,mod1-2,mod1),m1)
+mul(c2[i]*mod1%m1,qpow(mod1%mod2,mod2-2,mod2),m1);
t%=m1;
ll k=((c3[i]-t)%mod3+mod3)*qpow(m1%mod3,mod3-2,mod3)%mod3;
ll ans=((k%p)*(m1%p)+t%p)%p;
printf("%lld ",(ans+p)%p);
}
return 0;
}
5. 多项式其他运算
5.1. 多项式乘法逆
假设当前已经求出了 \(x^{\lceil\frac{n}{2}\rceil}\)，考虑如何推到原来的 x。
设此时的多项式为 \(B'\)，原来的为 \(B\)，显然和 A 相乘后 \(\bmod x^{\lceil\frac{n}{2}\rceil}\) 都是 1。
然后做差得到 \((B'-B)\equiv 0(\bmod x^{\lceil\frac{n}{2}\rceil})\)。
平方得到 \(B^2+B'^2-2BB' \equiv 0(\bmod x^{n})\)。
两边同乘 A，得到 \(AB'^2+B-2B' \equiv 0(\bmod x^{n})\)。
所以 \(B \equiv 2B'-AB'^2(\bmod x^{n})\)。
因为多出来的高次项对答案没有影响，所以直接递推上去就行了。
5.2. 多项式开根
按照上面的方法，考虑设 \(B'^2\equiv A(\bmod x^{\lceil\frac{n}{2}\rceil})\)
那么有 \(B^2-B'^2\equiv 0(\bmod x^{\lceil\frac{n}{2}\rceil})\)
平方得到：\(B^4+B'^4-2B^2B'^2\equiv 0(\bmod x^n)\)
有 \(B^4+B'^4+2B^2B'^2\equiv 4B^2B'^2(\bmod x^n)\)
两边开根得到：\(B^2+B'^2\equiv 2BB'(\bmod x^n)\)
因为 \(B^2\equiv A(\bmod x^n)\)，代换再整理得到：
\(B\equiv \dfrac{A+B'^2}{2B'}\)
浙公网安备 33010602011771号