快速数论变换(Fast Number-Theoretic Transform)，简称NTT(FNTT)。

然而这货和FFT基本上一样，就是求 $A(x)B(x)$ ，只不过系数要对 $p$ 取模。

原根

如果 $g$ 满足 $g^{i}\not\equiv g^{j}(mod\ p),i\not=j$ ，那么称 $g$ 为模 $p$ 意义下的原根。也就是说 $g$ 的次幂能够不遗漏也不重复的取到 $0\sim p-1$ 的所有值，周期为 $\varphi(p)$ ，当 $p$ 为素数的时候为 $p-1$ ，接下来都考虑 $p$ 为素数的情况。

这个性质非常的好，我们可以得到 $g^{p}\equiv g(mod\ p)\Rightarrow g^{p-1}\equiv 1(mod\ p)$ ，然后会觉得这个东西怎么这么像 $\omega_n^n=1$ 呢？所以我们令 $g_n=g^{(p-1)/n}$ ，那么只要我们说明原根也有类似单位复数根的性质，就可以把 $g$ 直接当做 $\omega$ 来用了。

$$ \begin{aligned} 1.&g_{2n}^{2k}=g^{2k(p-1)/2n}=g^{k(p-1)/n}=g_{n}^{k}\\ 2.&g_{n}^{n/2}=\pm\sqrt{g_n^{n}}\\ &∵ g^{i}\not=g^{j}\\ &∴ g_{n}^{n/2}=-1\\ 3.&(g_{n}^{k})^2=g_{n}^{2k}=g_{n\over 2}^{k} \end{aligned} $$

竟然都一样啊，那就很愉快了，至于原根怎么求之后再说。

快速数论变换

首先你要会背FFT板子，然后你把所有单位复数根换成原根就行了。注意模数需要是 $p=a\times 2^{k}+1$ 的形式，其中 $2^k\ge n$ ，$n$ 为补成二的次幂后得到的数，至于为什么就是防止指数出现分数导致没法处理。所以NTT模数要求比较严格……因此称为NTT模数QAQ，最著名(?)的应该是998244353(好像也叫UOJ模数，雾)。有没有任意模数NTT？安利Manchery的三模数NTT(反正我不会)，还有种比较粗暴的拆系数FFT也可以处理此问题。

板子：UOJ34，假装有模数。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=262144,MOD=998244353; //3是998244353的一个原根

int n,m,A[maxn+5],B[maxn+5],C[maxn+5],G[2][maxn+5],REV[maxn+5];

inline int Pow(int w,int b) {
    static int s;s=1;
    while (b) {if (b&1) s=(LL)s*w%MOD;b>>=1;if (b) w=(LL)w*w%MOD;}
    return s;
}
inline void Make(int n){
    for (int i=2;i<=n;i<<=1) G[0][i]=Pow(3,(MOD-1)/i),G[1][i]=Pow(G[0][i],MOD-2);
    for (int i=1;i<n;i++) REV[i]=(REV[i>>1]>>1)|((i&1)*(n>>1));
}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline void NTT(int *a,int n,int f){
    for (int i=0;i<n;i++) if (i>REV[i]) swap(a[i],a[REV[i]]);
    for (int k=1;k<n;k<<=1){
        int gn=G[f<0][k<<1],g=1,x,y;
        for (int i=0;i<n;i+=(k<<1),g=1)
            for (int j=0;j<k;j++,g=(LL)g*gn%MOD)
                x=a[i+j],y=(LL)a[i+j+k]*g%MOD,AMOD(a[i+j]=x,y),AMOD(a[i+j+k]=x,MOD-y);
    }
    if (f<0) for (int i=0;i<n;i++) a[i]=(LL)a[i]*Pow(n,MOD-2)%MOD;
}
int main(){
    freopen("NTT.in","r",stdin);
    freopen("NTT.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=0;i<=n;i++) scanf("%d",&A[i]);
    for (int i=0;i<=m;i++) scanf("%d",&B[i]);
    m+=n;for (n=1;n<=m;n<<=1);Make(n);NTT(A,n,1);NTT(B,n,1);
    for (int i=0;i<n;i++) C[i]=(LL)A[i]*B[i]%MOD;NTT(C,n,-1);
    for (int i=0;i<=m;i++) i?printf(" %d",C[i]):printf("%d",C[i]);
    return puts(""),0;
}

求原根

等等，放完代码就想跑？你还没讲怎么求原根呢！

好吧，其实求原根是暴力枚举我会告诉你？但是 $O(p)$ 验证肯定不行，所以我们来Orz Candy?

可以证明满足 $g^r≡1(mod\ p)$ 的最小的 $r$ 一定是 $p−1$ 的约数
对于质数 $p$ ，质因子分解 $p−1$，若 $g^{p−1\over p_i}\not=1(mod\ p)$ 恒成立，$g$ 为 $p$ 的原根

由于原根一般比较小，所以爆枚然后用上面那个来判断就行了（再说模数一般是固定的，先爆出来原根不就行了）。