快速数论变换 | NTT 初学

前置

FFT
原根

阶：称满足同余方程 \(a^x\equiv 1\mod m\) 的最小正整数解 \(x\) 为 \(a\) 的模 \(m\) 的阶，记为
\(Ord_ma\)。

观察到本质就是最短循环节，同时该同余方程类似于欧拉定理：

\[a^{\varphi (m)}\equiv 1\mod m，a\bot m \]
那么显然两者的关系是 \(Ord_ma\mid \varphi(m)\)。特别地，当 \(Ord_ma=\varphi(m)\) 时，我们称 \(a\) 是 \(m\) 的一个原根。

下面给出三个有关原根和阶的事实。
- 若有 \(a^n\equiv 1\mod m\)，则 \(a\) 的阶 \(x\) 满足 \(x\mid n\)。
  
  证明：
  
  将 \(n\) 带余除法表示成 \(xq+r(q\in Z,0\le r<x)\) 的形式，其中，\(x=Ord_ma\)。那么显然有 \(a^{xq}\equiv (a^x)^q\equiv 1^q\equiv 1\mod m\)。那么可得
  
  \[ a^r\equiv a^{n-xq}\equiv a^{n-xq}a^{xq}\equiv a^n\equiv 1\mod m \]
  因为 \(x\) 是满足 \(a^x\equiv 1\mod m\) 的最小正整数解，故有 \(r=0\)，也即 \(n=xq\)，故 \(x\mid n\)。
- 一个数 \(x\) 是模 \(m\) 的原根当且仅当 \(x\) 可以生成所有的可逆元，也即任何与 \(m\) 互质的整数 \(a\)，\(\exists k\)，\(a\equiv x^k\mod m\)。
  
  证明：
  
  若 \(x\) 不是模 \(m\) 的原根，那么其阶必定 \(<\varphi(m)\)，不同于 \(x\) 的次方就少于 \(\varphi(m)\) 个，但是可逆元是数量为 \(\varphi(m)\)，显然不可以生成所有可逆元。
  
  若 \(x\) 是模 \(m\) 的原根，\(x\) 的前 \(\varphi(m)\) 个正整数次方分别为 \(g,g^2,g^3,\cdots,g^{\varphi(m)}\)。我们尝试用反证法说明这 \(\varphi(m)\) 个数模 \(m\) 的结果互不相同。假设存在 \(1\le i<j\le \varphi(m)\) 满足 \(g^i\equiv g^j\mod m\)。那么必定有 \(g^{j-i}\equiv 1\)，因为 \(j-i<\varphi(m)\)，显然与 \(Ord_mx=\varphi(m)\) 矛盾。
  
  所以有 \(x\) 前 \(\varphi(m)\) 次方对 \(m\) 取模的余数恰好是与 \(m\) 互质的 \(\varphi(m)\) 个余数的重排后的结果，并且有 \(g^{\varphi(m)}=1\mod m\)。
- 设 \(x\) 是模 \(m\) 的一个原根，那么 \(x^k\) 是原根，当且仅当 \(\gcd(k,\varphi (m))=1\)。
  
  证明：
  
  当 \(k\) 与 \(\varphi(m)\) 互质时，一定可以找到一组 \((a,b)\) 满足 \(ak+b\varphi(m)=1\)。故对于 \(x\) 任意次方 \(x^i\) 都有：
  
  \[x^i\equiv x^{i(ak+b\varphi(m))}\equiv(x^k)^{ai}\mod m \]
  也即，\(x^i\) 在同于意义下可以表示成 \(x^k\) 的 \(ai\) 次方，这说明 \(x^i\) 可生成所有可逆元，故 \(x^i\) 为模 \(m\) 的逆元。
原根的存在性：
原根存在的充要条件是模数能表示成 \(2,4,p^n,2p^n\)，其中 \(p\) 是一个奇质数。其数量为 \(\varphi(\varphi(m))=\varphi(m-1)\)。

原根要怎么求？由前面有关原根的事实可知，要判断一个数 \(x(1<x<m)\) 是否是 \(m\) 的原根，将 \(m - 1\) 质因数分解成 \(p_1^{c_1}p_2^{c_2}\cdots p_k^{c_k}\)。那只需要检验 \(\tfrac{x(m-1)}{p_1},\tfrac{x(m-1)}{p_2},\cdots,\tfrac{x(m-1)}{p_k}\) 中是否存在一个数 \(v\) 使得 \(v\equiv 1\mod x\)。时间复杂度 \(O(k\log m)\)，其中 \(k\) 为 \(m-1\) 的质因子个数。当 \(m<10^{18}\) 时，\(k\le 25\)，时间开销极小。

NTT

快速傅里叶变换中选定单位根做多项式乘法，其劣势在于无法保证浮点数的精度。考虑用原根替换，会发现它依然满足单位根的三个引理：消去引理、折半引理、求和引理。

void NTT(int *e, int op) {
  for(int i = 0; i < lim; i++) {
		if(i < p[i]) swap(e[i], e[p[i]]); // 蝴蝶变换
	}
	for(int k = 1; k < lim; k <<= 1) { // 迭代
		long long pw = Pow((op == -1 ? Pow(3, Mod - 2) : 3), (Mod - 1) / (k << 1)); // 原根替换单位根
		for(int i = 0; i < lim; i += k << 1) { 
			for(int j = i, o = 1; j < i + k; j++, o = o * pw % Mod) {
				int x = e[j];
				int y = e[j + k];
				e[j] = (x + y * o % Mod) % Mod;
				e[j + k] = (x - y * o % Mod + Mod) % Mod;
			}
		}
	}
	if(op == -1) {
		for(int i = 0; i < lim; i++) {
			e[i] = e[i] * Pow(lim, Mod - 2) % Mod;
		}
	}
}