快速数论变换 | NTT 初学
前置
-
原根
阶：称满足同余方程 \(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;
}
}
}
FFT/NTT 匹配字符串
现有文本串 \(s\), 模式串 \(t\)，长度分别为 \(ls\)，\(lt\)。规定下标均从 \(0\) 开始。为方便处理，先要将字符串都转成整数。
设 \(t\) 与 \(s\) 在 \(s\) 的下标 \(p\) 结尾处匹配上，也即对于 \(i=0\sim lt - 1\)，有 \(s_{p-lt+i+1}=t_i\)。
因为完全匹配，所以有
\[\sum\limits_{i=0}^{lt-1}(s_{p-lt+i+1}-t_i)^2=0 \]\[\sum\limits_{i=0}^{lt-1}(s_{p-lt+i+1}^2 +t_i^2-2s_{p-lt+i+1}t_i)=0 \]为了统一下标，将 \(t\) 反转。
\[\sum\limits_{i=0}^{lt-1}(s_{j}^2 +t_i^2-2s_{j}t_i)=0,(i+j=p) \]这样就可以用FFT/NTT 求解了。
标签：原根,数论,NTT,varphi,lt,初学,mod,equiv From： https://www.cnblogs.com/ereoth/p/17922454.html