NTT学习笔记（快速数论变换）

一些概念

欧拉函数$\varphi (n)$

欧拉函数简介

阶

若$g$和$n$互质，则令$g^x\%n=1$的最小正整数$x$称为$g$模$n$的阶。

原根

对于互质的两个正整数$g$和$n$，如果$g$模$n$的阶为$\varphi (n)$，则称$g$为$n$的原根。

求原根

一般的原根都比较小，暴力枚举即可。

NTT

前置知识：快速傅里叶变换（$FFT$）

在$FFT$中，我们选择$n$次单位复根作为$x$的值，因为他们满足消去引理、折半引理、求和引理，所以可以用分治的方法将时间复杂度变为$O(n\log n)$。但因为用了复数，所以在精度上有误差。而在一些题目要求的是带模的多项式乘法，所以$FFT$就用不了了。那么，我们能不能让$x$取整数值，使得这个值也能满足消去引理、折半引理、求和引理呢？

设$\varphi (m)=r\times 2^d$，令$n=2^d$，$x_n^i=x^{\varphi (m)\times i/n}(\mathrm{mod}m)$，其中$i\le n$

则$x_n^i$有以下性质：

1. 消去引理

$$x_{dn}^{dk}=x_n^k(\mathrm{mod}m)$$

证明：$x_{dn}^{dk}=x^{\varphi (m)\times dk/dn}=x^{\varphi (m)\times k/n}=x_n^k(\mathrm{mod}m)$

2. 折半引理

$$(x_n^{k+n/2}{)}^2=x_{n/2}^k(\mathrm{mod}m)$$

证明：$(x_n^{k+n/2}{)}^2=x_n^{2k+n}=x_n^{2k}=x_{n/2}^k(\mathrm{mod}m)$

3. 求和引理

$$\sum _{i=0}^{n-1}(x_n^k{)}^j=0(\mathrm{mod}m)$$

证明：$\sum _{i=0}^{n-1}(x_n^k{)}^j=\frac{1-(x_n^k{)}^n}{1-x_n^k}=\frac{0}{1-x_n^k}=0$

那么，用$x$来代替$FFT$中的$\omega$，其他不变，就可以求带模数的多项式乘法了。

模数的限制

若模数$m=r\times 2^k+1$（其中$r$为奇数，$k$为整数），则多项式乘积的次数不能超过$2^k$。

如果题目没有模数，那也可以取一个较大的模数，保证答案的每一位都小于这个模数，用这个模数来做$NTT$也是可以的。

一些模数的原根

模数	原根	最大长度
$998244353=119\times 2^{23}+1$	$3$	$2^{23}$
$469762049=7\times 2^{26}+1$	$3$	$2^{26}$
$2281701377=17\times 2^{27}+1$	$3$	$2^{27}$

例题

多项式乘法（FFT）

#include<bits/stdc++.h>
using namespace std;
const long long g=3,mod=998244353;
long long w,wn,a1[5000005],a2[5000005];
long long mi(long long t,long long v){if(v==0) return 1;long long re=mi(t,v/2);re=re*re%mod;if(v&1) re=re*t%mod;return re;
}
void ch(long long *a,int l){for(int i=1,j=l/2,k;i<l-1;i++){if(i<j) swap(a[i],a[j]);k=l/2;while(j>=k){j-=k;k>>=1;}j+=k;}
}
void ntt(long long *a,int l,int fl){for(int i=2;i<=l;i<<=1){if(fl==1) wn=mi(g,(mod-1)/i);else wn=mi(g,mod-1-(mod-1)/i);for(int j=0;j<l;j+=i){w=1;for(int k=j;k<j+i/2;k++,w=w*wn%mod){long long t=a[k],u=w*a[k+i/2]%mod;a[k]=(t+u)%mod;a[k+i/2]=(t-u+mod)%mod;}}}if(fl==-1){long long ny=mi(l,mod-2);for(int i=0;i<l;i++) a[i]=a[i]*ny%mod;}
}
int main()
{int n=1,l1,l2;scanf("%d%d",&l1,&l2);++l1;++l2;while(n<l1+l2) n<<=1;for(int i=0;i<l1;i++){scanf("%lld",&a1[i]);}for(int i=0;i<l2;i++){scanf("%lld",&a2[i]);}ch(a1,n);ch(a2,n);ntt(a1,n,1);ntt(a2,n,1);for(int i=0;i<n;i++){a1[i]=a1[i]*a2[i]%mod;}ch(a1,n);ntt(a1,n,-1);for(int i=0;i<l1+l2-1;i++) printf("%lld ",a1[i]);return 0;
}