阶与原根
阶
若正整数 \(m, \ a\)，满足 \((a, m) = 1\)，则使 \(a^n\equiv 1 \pmod m\) 的最小正整数 \(n\) 称为 \(a\) 模 \(m\) 的阶，记作 \(\delta_m(a)\)。
\(\delta_7(1) = 1, \ \delta_7(2) = 3, \ \delta_7(3) = 6\)。
原根
若 \(\delta_m(a) = \varphi(m)\)，则称 \(a\) 为 \(m\) 的一个原根。
欧拉定理：若 \((a, m) = 1\)，则 \(a^{\varphi(m)}\equiv 1\pmod m\)。
阶的性质
假设 \((a, m) = 1, \ \delta = \delta_m(a)\)，则
-
\(a^0, a^1, \dots, a^{\delta - 1}\) 在模 \(m\) 意义下两两不同。
证明：
如果存在 \(a^x \equiv a^y \pmod m, \ x < y \le \delta - 1\)。
则 \(a^{y - x} \equiv 1\)，且 \(y - x < \delta\)，与阶的最小性矛盾。
-
\(a^{\gamma}\equiv a^{\gamma'} \pmod m \iff \gamma \equiv \gamma'\pmod \delta\)。
-
\(\delta \mid \varphi(m)\)。
证明：
令 \(\varphi(m) = q\delta + r, \ (0 \le r < \delta)\)。
如果 \(r > 0\)，则 \(a^{q\delta + r} \equiv a^{r} \equiv a^{\varphi(m)}\equiv 1 \pmod m\)，则有 \(r < \delta\)，与 \(\delta_m(a) = \delta\) 矛盾。
所以 \(r = 0\)。
-
设 \(m \in\mathbb{N^*}, \ a, b\in \mathbb{Z}, \ (a, m) = (b, m) = 1\)，则
\[\delta_m(ab) = \delta_m(a)\delta_m(b) \]的充要条件为 \((\delta_m(a), \delta_m(b)) = 1\)。
-
设 \(k\in \mathbb{N}, \ m \in \mathbb{N^*}, \ a\in \mathbb{Z}, \ (a, m) = 1\)，则
\[\delta_m(a^k) = \dfrac{\delta_m(a)}{(\delta_m(a), k)} \]证明：
注意到：
\[\begin{aligned} & a^{k\delta_m(a^k)}=(a^k)^{\delta_m(a^k)}\equiv 1 \pmod m \\ \implies & \delta_m(a)\mid k\delta_m(a^k) \\ \implies & \dfrac{\delta_m(a)}{\left(\delta_m(a),k\right)}\mid\delta_m(a^k) \end{aligned} \]另一方面，由 \(a^{\delta_m(a)}\equiv 1 \pmod m\)，可知：
\[(a^k)^{\frac{\delta_m(a)}{(\delta_m(a),k)}}=(a^{\delta_m(a)})^{\frac{k}{(\delta_m(a),k)}}\equiv 1 \pmod m \]故：
\[\delta_m(a^k)\mid\dfrac{\delta_m(a)}{(\delta_m(a),k)} \]综合以上两点，得：
\[\delta_m(a^k)=\dfrac{\delta_m(a)}{(\delta_m(a),k)} \]
原根的存在与判定
原根的存在定理
只有模 \(2,\ 4,\ p^a,\ 2p^a\) （\(p\) 是奇质数）存在原根。
原根的判定定理
设 \(m > 1\)，\(g\) 为正整数且 \((g, m) = 1\)。则 \(g\) 是 \(m\) 的原根当且仅当对于任意 \(\varphi(m)\) 的质因子 \(q_i\)，\(g^{\varphi(m)/q_i} \not\equiv 1 \pmod m\)。
证明：如果 \(\delta < \varphi(m)\) 且 \(\delta \mid \varphi(m)\)，则一定存在一个 \(q_i\) 使得 \(\delta \mid\varphi(m) / q_i\)。
原根个数
若 \(m\) 有原根，则它原根的个数为 \(\varphi(\varphi(m))\)。
证明：
若 \(m\) 有原根 \(g\)，则：
\[\delta_m(g^k)=\dfrac{\delta_m(g)}{\left(\delta_m(g),k\right)}=\dfrac{\varphi(m)}{\left(\varphi(m),k\right)} \]所以若 \(\left(k,\varphi(m)\right)=1\)，则有：\(\delta_m(g^k)=\varphi(m)\)，即 \(g^k\) 也是模 \(m\) 的原根。
而满足 \(\left(\varphi(m),k\right)=1\) 且 \(1\leq k \leq \varphi(m)\) 的 \(k\) 有 \(\varphi(\varphi(m))\) 个。所以原根就有 \(\varphi(\varphi(m))\) 个。
指标（离散对数）
定义
对于质数 \(p\)，假设 \(g\) 是 \(p\) 的一个原根，则 \(g^0, \ g^1, \dots, g^{p - 2}\) 在模 \(p\) 意义下是 \(1, 2, \dots, p - 1\) 的一个排列。
假设对于 \(x \in [1, p)\) 有 \(g^c\equiv x \pmod p\)，则称 \(x\) 的指标为 \(c\)，记作 \(\operatorname{ind}(x) = c\)（或 \(\operatorname{ind}_g(x) = c\)）。
性质
对于任意 \(x, y \in [1, p)\)，存在
\[\begin{aligned} \operatorname{ind}(xy) &= \operatorname{ind}(x) + \operatorname{ind}(y)\pmod {\varphi(p)}\\ \\ \operatorname{ind}(x^c) &= c\operatorname{ind}(x)\pmod {\varphi(p)}\\ \end{aligned} \]类似于实数运算中的对数，因此指标亦称离散对数。
baby step giant step (BSGS)
给定质数 \(p\)，求最小满足 \(g^c \equiv x \pmod {p}\) 的非负整数 \(c\) 的值。
令 \(c = aB + b\)，其中 \(B = \lceil\sqrt{p}\rceil\)。
因为 \(c < \varphi(p) = p - 1\)，所以 \(a, \ b < B\)。
-
BS：枚举 \(b = 0, \ 1, \ \dots, B - 1\)，将 \(xg^{b}\) 计入哈希表。
-
GS：枚举 \(a = 1, \ 2, \ \dots, B\)，若存在 \(g^{aB} = xg^b\)，则最小满足条件的 \(c = aB - b\)。
最小性证明：
对于 \(xg^b \bmod p\) 相同的 \(b\)，大的会在哈希表中覆盖小的，从而使 \(aB - b\) 最小。
\(B > b\)，所以 \(a\) 对答案的贡献大于 \(b\)，从小到大枚举 \(a\) 使答案最小。
例题
Discrete Roots
题意：给出两个质数 \(p, k\) 和一个整数 \(a\)，求 \(x^k = a \pmod p\) 的所有解。
\[\begin{aligned} &\operatorname{ind}(x^k) = k\operatorname{ind}(x) = \operatorname{ind}(a) \pmod{\varphi(p)}\\ \\ &k\operatorname{ind}(x) \equiv\operatorname{ind}(a)\pmod{\varphi(p)}\\ \\ &x \equiv g^{\operatorname{ind}(x)} \pmod p \end{aligned} \]所以只需处理 \(p\) 的原根以及 \(a\) 的指标，中间的同余方程可用 exgcd 求解。
特判 \(a = 0\) 的情况。
快速数论数论变换(NTT)
即把 FFT 中 \(\mathbb{C}\) 上的运算变成 \(\mathbb{Z}_p\) 上的运算。
-
假设素数 \(p\) 满足 \(p = r2^l + 1\)，\(g\) 是 \(p\) 的原根。
-
用 \(g_n = g^{\frac{p - 1}{n}}\) 替代 \(\omega_n\)。
-
\(g_{2n}^{2k} \equiv g_n^k \pmod p， \ (2n < 2^l)\)。
-
\(g_{2n}^{n} \equiv -1 \pmod p, \ (2n < 2^l)\)。
\(g_{2n}^n = g^{\frac{p - 1}{2}}\)。
由于 \((g^{\frac{p - 1}{2}})^2 \equiv g^{p - 1} \equiv 1\pmod p\)，所以 \(g_{2n}^n\) 只可能同余 \(1\) 或 \(-1\)。
又因为 \(g\) 为原根，\(\delta_{p}(g) = p - 1\)。
若 \(g^{\frac{p - 1}{2}} \equiv 1\) 则与阶的最小性矛盾，所以 \(g^{\frac{p - 1}{2}}\equiv-1\pmod p\)。
-
\(\sum_{k = 0}^{n - 1}g_{n}^{ik}g_{n}^{-kj} \equiv \begin{cases} n & i = j\\ 0 & i \neq j \end{cases}\pmod p\)，其中 \(i, j \in [0, n)\)。
优点：快，精确。
限制：模数要满足 \(p = 2^l + 1\)。
常见模数：
-
\(65537 = 2^{16} + 1, \ g = 3\)。
-
\(998244353 = 119 \cdot 2^{23} + 1, \ g = 3\)。
-
\(1004535809 = 479 \cdot 2^{21} + 1, \ g = 3 \quad > 10^{9}\)。
-
\(4179340454199820289 = 29 \cdot 2^{57} + 1, \ g = 3 \quad> 4\cdot 10^{18}\)。
分治 FFT(NTT)
-
在模 \(998244353\) 意义下，计算 \(f(x) = \prod (x - a_i)\) 的各项系数。
-
计算 \([l, mid]\) 之积。
-
计算 \([mid + 1, r]\) 之积
-
\([l, mid]\) 与 \([mid + 1, r]\) 相乘。
时间复杂度 \(O(n\log^2n)\)。
-
-
在模 \(998244353\) 意义下，计算 \(f(x) = \prod f_i(x)\) 的各项系数，其中 \(\sum\deg(f_i(x)) \le 10^5\)。
可以和上题一样分治。
也可以按照次数维护一个优先队列，每次相乘当前最小的两个，即一棵哈夫曼树。