乘法
NTT
构造模意义单位根。
发现 δpgk=gcd(k,p−1)(p−1),当 n∣(p−1) 时, δpg(p−1)/n=gcd(np−1,p−1)(p−1)=n
令 ωn=g(p−1)/n ,则 ωn0,ωn1,⋯,ωnn−1 互不相同,且有:
- ω2n2k=(g(p−1)/2n)2k=(g(p−1)/n)k=ωnk。
- wnn=gp−1=1
- ωnn/2=g(p−1)/2=−1(任何数 a 满足 aφ(p)/2≡±1(modp),显然 gφ(p)/2=1)
- ωnk+n/2=−ωnk
一些实现上的细节:
- 使用
unsigned long long
,避开部分取模
- 关于代码中的
std::reverse(f + 1, f + n)
:
(咕)