快速数论变换NTT

快速数论变换(NTT)

一.相关概念:

1.剩余系: 一个整数去模n得到的结果的集合称为n的简化剩余系,即小于n的非负整数,记为Zn​
2.简化剩余系: 在n的剩余系中与n互质的元素的集合,称为n的简化剩余系,记为Zn∗​
3.欧拉函数: n的简化剩余系中元素的个数,称为欧拉函数,记为ϕ(n)
3.原根: 对于正整数x和n,如果x模n的阶为ϕ(n),则称x为n的原根.换句话说,即对于1≤j<ϕ(n),使得xj̸​=1(mod n),但xϕ(n)=1(mod n)则称x为n的原根.
如何求原根?
求n的原根,似乎只能暴力枚举g(2≤g≤n−1),然后检测gpmod n是否等于1,此处p为xϕ(n)​,x为ϕ(n)的质因数.如果存在一个p使得gpmod n等于1,则g不是原根,否则g为原根.
一般原根都很小,所以暴力枚举即可.

二.NTT

在FFT中,我们精心的选择了n次单位复根,因为它们符合消去引理、折半引理和求和引理，于是可以采用分治的方法将时间复杂度将为O(NlogN).但是因为使用了复数,所以在精度上可能会有些误差.那么能不能找到其他的值,使得他们也能符合消去引理、折半引理和求和引理呢？
在数论当中，我们发现某些数的简化剩余系在模运算下符合这个性质。如果m存在原根x,则m的简化剩余系Zm∗​={xj(mod m)∣1≤j≤ϕ(n)}.
设ϕ(m)=k∗2n, xi​=xϕ(m)/i(mod m) ,i也为2的幂,且i≤2n
则易知xi​满足:
1.消去引理
xidjd​=xij​(mod m)
2.折半引理:
(xij+i/2​)2=xi2j+i​=(xij​)2∗xii​=(xij​)2(mod m)
3.求和引理:
当m>2且k不是i的倍数时,下式成立:
j=0∑i−1​(xik​)j=0(mod m)
所以,我们可以取m的原根,像FFT一样,在O(NlogN)的时间内完成多项式乘法.
使用NTT时有些限制,如果多项式乘法不要求取模,则我们要找足够大的质数m,并且m−1=k∗2n,要保证n大于多项式的项数,m还要大于多项式的系数.
如果多项式乘法是带模乘法,则只能用NTT,不能使用FFT.此时,若m为质数,则要求m−1=k∗2n,n要大于多项式的系数.若m不为质数,则需要用中国剩余定理来做.
三.模板
使用NTT计算多项式的乘积

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
#define LL long long int
#define MAXN 400005
LL num1[MAXN],num2[MAXN];
int n,m,len;
const LL G=3;
const LL MOD=998244353;
LL w,wn;
LL ksm(LL x,LL k){
LL res=1;
    while(k)
    {
      if(k&1)
      res=res*x%MOD;
      x=x*x%MOD;
     k>>=1;
    }
    return res;}
void change(LL *num,int len){
    for(int i=1,j=len/2;i<len-1;i++)
    {
        if(i<j)swap(num[i],num[j]);
        int k=len/2;
        while(j>=k)
        {
            j-=k;
            k/=2;
        }
        if(j<k)j+=k;
    }}
void ntt(LL *num,int len,int flg){
    for(int i=2;i<=len;i<<=1)
    {
        if(flg==1)w=ksm(G,(MOD-1)/i);
        else w=ksm(G,MOD-1-(MOD-1)/i);
        for(int j=0;j<len;j+=i)
        {
            wn=1;
            for(int k=0;k<i/2;k++)
            {
              LL u=num[j+k],t=num[j+k+i/2]*wn%MOD;
              num[j+k]=(u+t)%MOD;
              num[j+k+i/2]=(u-t+MOD)%MOD;
              wn=wn*w%MOD;
            }
        }
    }
    if(flg==-1)
    {
        LL ni=ksm(len,MOD-2);
        for(int i=0;i<len;i++)
        num[i]=num[i]*ni%MOD;
}
}
int main()
{
 while(~scanf(\"%d%d\",&n,&m))
    {
        memset(num1,0,sizeof num1);
        memset(num2,0,sizeof num2);
        n++,m++;
    for(int i=0;i<n;i++)
    {
        scanf(\"%lld\",&num1[i]);
    }
    for(int i=0;i<m;i++)
    scanf(\"%lld\",&num2[i]);
    len=1;
        while(len<n+m-1) len<<=1;
        change(num1,len);
        change(num2,len);
        ntt(num1,len,1);
        ntt(num2,len,1);

        for(int i=0;i<len;i++)
        num1[i]=num1[i]*num2[i];
        change(num1,len);
        ntt(num1,len,-1);
        int pos=0;
        for(int i=0;i<n+m-1;i++)
        printf(\"%lld \",num1[i]);
        printf(\"\\n\");
    }
    
    return 0;
    }