NTT

[TOC]

据说这玩意算数学?

学,我学还不行么….

基础知识

原根

定义

对于两个正整数\((a,m)==1\),根据欧拉定理可知,\(\exists\ d\leq m-1,d=\varphi(m)\),使得\(a^d\equiv1( mod\ m)\)

对于每一个\(d,0\leq d\leq m-1\)都能使得\(a^d\equiv 1(\ mod\ m)\),则称\(a\)为模\(m\)的一个原根.

设\(m=7\),则\( \varphi (m) \) 等于\(6\)。
设\(a=2\),由于\(2^3 = 8 \equiv 1 \pmod{7} \),而\(\displaystyle 3 < 6 \),所以 \(2\) 不是模 \(7\) 的一个原根。
设\(a=3\),由于\(3^1 \equiv 3 \pmod{7} \),\(3^2 \equiv 2 \pmod{7} \),\(3^3 \equiv 6 \pmod{7} \),\(3^4 \equiv 4 \pmod{7} \),\(3^5 \equiv 5 \pmod{7} \),\(3^6 \equiv 1 \pmod{7} \),因此有\(Ord_7(3) = 6 =\varphi (7)\),所以 \(3\) 是模 \(7\) 的一个原根。

性质

类比FFT中用到的单位负根的几个性质

  • \(\omega_n^t (0\leq t\leq n-1)\)均不相同,确保计算点值的时候均为有效答案.

性质一:令\(\omega_n=g^q\),因为\(g^0,g^1,g^2,g^3,g^4,g^5……\)均不相同,故满足性质.

  • \(\omega_{2n}^{2k}=\omega_n^k,\omega_{n}^{k+\frac{n}{2}}=-\omega_{n}^{k}\),用于分治.

性质二:由\( \omega_n = g ^ q\)可知\( \omega_{2n} = g ^ { \frac{q}{2} }(p = \frac{q}{2} \times 2n + 1)\),故 \(\omega_{2n} ^ {2k} = g ^ {2k \frac{q}{2} } = g ^ {kq} = \omega_n ^ k\),故满足性质。

NTT

对于一般的多项式乘法而言,并不是所有参与运算的系数都是复数,并且存在复数运算之间的误差,那对于只有整数参与的多项式运算,也一样可以套用类似FFT的东西在\(O(nlog_2n)\)的时间内解决.我们称这种东西为NTT.

其他和FFT都一样辣.

一般来说,我们选择1004535809,或者998244353,这两个大质数的原根均为3.

代码实现


2018.03.14

10:23

发表评论

电子邮件地址不会被公开。 必填项已用*标注