多项式理论基础

FFT

FFT 理论回顾
算法实现，对于 $C(x) = A(x)B(x)$，$A(x)$ 幂指为 $m$，$B(x)$ 幂指为 $n$

步骤1，补 $0$，预处理处理位逆序置换，多项式卷积应该有 $tot$ 项，必须满足 $2^{tot} \geqslant (m+n+1)$
设系数向量为 $\bm{v}_1, \bm{v}_2$，这样得到两个 $O(2n)$ 多项式

步骤2，计算 $O(2n)$ 多项式的点表示法，$\bm{f}_1 = \text{DFT}(\bm{v}_1), \ \bm{f}_2 = \text{DFT}(\bm{v}_2)$
$\bm{f}_1, \bm{f}_2$ 就是两个多项式在 $O(2n)$ 次单位根处的点表示

步骤3，计算 $\bm{f}_1 \cdot \bm{f}_2$，向量每一维对应相乘，得到 $\bm{f}$

步骤4，计算 $\bm{v} = \text{IDFT}(\bm{f})$，其中 $\bm{f}$ 就是乘积的系数向量

具体到一些细节上

细节1
$\text{DFT}$ 和 $\text{IDFT}$ 可以统一起来
计算 $\text{DFT}$ 的时候，$\bm{v}$ 对应的第 $k$ 项，再对应到矩阵 $V_n$ 中的值为 $\omega_n^k$

实际上就是取决于单位根 $\displaystyle \omega_n = \text{e}^{2\pi i / n} = \cos \left(\frac{2\pi}{n} \right) + i \sin \left(\frac{2\pi}{n} \right)$
定义 $\omega = 1$，然后迭代 $k$ 次，每一次令 $\omega = \omega \cdot \omega_n$

$\text{IDFT}$ 呢？最终我们得到卷积第 $k$ 项系数 $a_k = \displaystyle \frac{1}{n} \cdot \omega_n^{-k}$
这取决于 $\displaystyle \omega_n^{-1} = \cos \left(\frac{2\pi}{n} \right) - i \sin \left(\frac{2\pi}{n} \right)$

同样可以定义 $\omega = 1$，迭代 $k$ 次，每次令 $\omega = \omega \cdot \omega_n^{-1}$

$\text{DFT}(\bm{v}, 1)$ 表示 $\text{DFT}$ 过程，$\text{DFT}(\bm{v}, -1)$ 就表示 $\text{IDFT}$，区别就在于 $i \sin$ 之前乘不乘 $-1$

细节2
自底向上归并，根据
左半边 $\displaystyle A(\omega_{n}^k) = A_0(\omega_{n/2}^k) + \omega_{n}^k A_1(\omega_{n/2}^k)$
右半边 $\displaystyle A(\omega_{n}^k) = A_0(\omega_{n/2}^k) - \omega_{n}^k A_1(\omega_{n/2}^k)$

归并的最底层，代入 $\omega_1^k = 1$，所以最底层，实际上就是相对应的多项式系数 $a_k$

令 $mid = n/2$，那么我们有
$\textbf{for} \quad mid\in [1, 2, 4, \cdots, O(2n)): \quad \textbf{for} \quad i \in [0, 2mid, 4mid, \cdots, O(2n))$

注意这里归并的最底层，$A(\omega_1^k) = \displaystyle \sum_{k}a_k$
一边迭代一边求 $\omega_n^k$，就是令 $\omega = 1$，然后每一次 $\omega = \omega \cdot \omega_n$

令 $j \in [0, mid-1)$，取出原来对应的 $x \leftarrow A[i+j], \quad y \leftarrow \omega_n^k \cdot A[i+j+mid]$
更新 $A[i+j] \leftarrow x+y, \quad A[i+j+mid] \leftarrow x-y$
然后不要忘记更新 $\omega = \omega \cdot \omega_n$

原根理论

常用结论

Euler 函数的不完全积性，当且仅当 $(n, m) = 1$ 时，$\varphi(nm) = \varphi(n) \varphi(m)$
当 $n = p^k$ 时，$\varphi(n) = p^k - p^{k-1}$

阶

满足 $a^n \equiv 1 (\bmod p)$ 的最小正整数 $n$ 存在，这个 $n$ 称为 $a$ 模 $p$ 的阶，记为 $\delta_p(a)$

性质1
$\left<a, a^2, a^3, \cdots, a^{\delta_p(a)} \right>$ 两两互不同余

考虑反证法，如果存在 $a^i \equiv a^j (\bmod p)$，那么 $a^{i - j} \equiv 1(\bmod p)$
但是 $|i - j| < \delta_p(a)$，这与阶的定义矛盾

性质2
如果 $a^n \equiv 1 (\bmod p)$，那么 $\delta_p(a) \mid n$，也可以推出 $\delta_p(a) \mid \phi(p)$

我们有 $n = \delta_p(a) \cdot q + r, \quad 0 \leqslant r \leqslant \delta_p(a)-1$
如果 $r > 0$，那么有 $\displaystyle a^r \equiv a^n \cdot \left(a^{\delta_p(a)} \right)^{-q} \equiv 1(\bmod p)$
因为 $r \in [1, \delta_p(a)-1]$，与阶的最小性矛盾，所以 $\delta_p(a) \mid n$

推论1
若有 $a^p \equiv a^q(\bmod m)$，那么有 $p \equiv q (\bmod \ \delta_m(a))$

很显然，移项之后有 $\delta_m(a) \mid (p - q)$

阶的混合运算
如果 $\textbf{gcd}(a, m) = 1$，那么下面记 $a \bot m$

性质3，设 $m \in \mathbb{N}^{*}, \ a, b \in \mathbb{Z}$，如果 $a \bot m, b \bot m$，则
$\displaystyle \delta_m(ab) = \delta_m(a) \delta_m(b)$ 的充分必要条件是
$\displaystyle \textbf{gcd}(\delta_m(a), \delta_m(b)) = 1$

必要性，因为 $a^{\delta_m(a)} \equiv 1(\bmod \ m)$ 以及 $b^{\delta_m(b)} \equiv 1 (\bmod \ m)$
那么 $\displaystyle (ab)^{\text{lcm}(\delta_m(a), \delta_m(b))} \equiv 1 (\bmod \ m)$
根据阶的性质，我们有 $\displaystyle \delta_m(ab) \mid \text{lcm}(\delta_m(a), \delta_m(b))$
根据条件 $\delta_m(ab) = \delta_m(a) \delta_m(b)$，可以知道 $\displaystyle \delta_m(a) \delta_m(b) \mid \text{lcm}(\delta_m(a), \delta_m(b))$
即 $\text{gcd}(\delta_m(a), \delta_m(b)) = 1$

充分性，我们已知 $\text{gcd}(\delta_m(a), \delta_m(b)) = 1$
由 $(ab)^{\delta_m(ab)} \equiv 1(\bmod m)$ (阶的定义)，我们有
$\displaystyle 1 \equiv (ab)^{\delta_m(ab)} = 1 \equiv (ab)^{\delta_m(ab) \delta_m(b)}$，这一步如果有异议，可以这么看
$a\bot m, b\bot m$，所以 $(ab) \bot m$，那么 $(ab)^{\delta_m(ab)} = km + 1$，那么 $\displaystyle \left((ab)^{\delta_m(ab)}\right)^p = (1+km)^p \equiv 1 (\bmod \ m)$
由此 $\displaystyle 1 \equiv (ab)^{\delta_m(ab) \delta_m(b)} \equiv a^{\delta_m(ab) \delta_m(b)} (\bmod \ m)$
那么根据性质 2，我们有 $\delta_m(a) \mid \delta_m(ab) \delta_m(b)$，因为 $\delta_m(a) \bot \delta_m(b)$，所以我们有
$\delta_m(a) \mid \delta_m(ab)$，对称地也有 $\delta_m(b) \mid \delta_m(ab)$
综上所述，我们有 $\delta_m(a) \delta_m(b) \mid \delta_m(ab)$
另一方面，我们有 $(ab)^{\delta_m(a) \delta_m(b)} \equiv \left(a^{\delta_m(a)} \right)^{\delta_m(b)} \cdot \left(b^{\delta_m(b)} \right)^{\delta_m(a)} \equiv 1(\bmod \ m)$
所以 $\delta_m(ab) \mid \delta_m(a) \delta_m(b)$，综上所述 $\delta_m(ab) = \delta_m(a) \delta_m(b)$

性质4
设 $k \in \mathbb{N}, m \in \mathbb{N}^{*}, \ a \in \mathbb{Z}$，如果 $(a, m) = 1$，即 $a \bot m$，那么

$$\delta_m(a^k) = \frac{ \delta_m(a) }{\text{gcd}(\delta_m(a), k)}$$

首先，$a \bot m$，那么如果 $k \in \mathbb{N}$，有 $a^k \bot m$，这个之前用 $a^k = (pm + 1)^k \equiv 1(\bmod m)$ 证明过了
注意到 $\displaystyle a^{(k \cdot \delta_m(a^k))} = \left(a^k \right)^{\delta_m(a^k)} \equiv 1(\bmod \ m)$
由此 $\delta_m(a) \mid k \delta_m(a^k)$
$\Rightarrow \displaystyle \frac{\delta_m(a)}{\text{gcd}(\delta_m(a), k)} \mid \delta_m(a^k)$

另一方面，因为 $a^{\delta_m(a)} \equiv 1 (\bmod m)$，可以知道

令 $\displaystyle r = \frac{k}{\text{gcd}(k, \delta_m(a))}$，那么 $\displaystyle a^{r \cdot \delta_m(a)} \equiv 1(\bmod m)$

$\displaystyle \left(a^k \right)^{\frac{\delta_m(a)}{\text{gcd}(\delta_m(a), k)}} = \left(a^{\delta_m(a)} \right)^{\frac{k}{\text{gcd}(\delta_m(a), k)}} \equiv 1 (\bmod m)$

从而有 $\displaystyle \delta_m(a^k) \mid \frac{\delta_m(a)}{\text{gcd}(\delta_m(a), k)}$，从而 $\displaystyle \delta_m(a^k) = \frac{\delta_m(a)}{\text{gcd}(\delta_m(a), k)}$

原根

设 $m \in \mathbb{N}^{*}, \ a \in \mathbb{Z}$，如果 $(a, m) = 1$，并且 $\delta_m(a) = \varphi(m)$
称 $a$ 为模 $m$ 的原根

原根判定定理
假设 $m \geqslant 3$，如果 $(a, m) = 1$，则 $a$ 是模 $m$ 的原根的充要条件是，对于 $\varphi(m)$ 的每个素因子 $p$
都有 $\displaystyle a^{\varphi(m) / p} \not \equiv 1(\bmod m)$

必要性是显然的，否则 $\varphi(m) / p$ 应该是 $a$ 在模 $m$ 意义下的阶了，下面证明充分性
对于 $\varphi(m)$ 的每个素因子 $p$，都有 $a^{\varphi(m) / p} \not \equiv 1 (\bmod m)$ 成立时，如果有一个 $a$
不是模 $m$ 的原根，那么存在 $t < \varphi(m)$，使得 $a^t \equiv 1(\bmod m)$
那么根据 Bézout’s 定理，一定存在 $(x, y)$，使得 $t \cdot x + \varphi(m) \cdot y = \text{gcd}(t, \varphi(m))$
换句话说，我们能找到 $(k, x)$，使得 $kt = x\varphi(m) + \text{gcd}(t, \varphi(m))$
根据 Euler 定理，我们有 $\displaystyle a^{\varphi(m)} \equiv 1 (\bmod \ m)$，所以
$\displaystyle 1 \equiv a^{kt} = a^{x\varphi(m) + \text{gcd}(t, \varphi(m))} \equiv a^{\text{gcd}(t, \varphi(m))} (\bmod \ m)$

因为 $\text{gcd}(t, \varphi(m)) \mid \varphi(m)$ 并且 $\text{gcd}(t, \varphi(m)) \leqslant t < \varphi(m)$

根据 $\text{gcd}(t, \varphi(m)) < \varphi(m)$，一定存在 $\varphi(m)$ 的素因子 $p$，使得 $\displaystyle \text{gcd}(t, \varphi(m)) \mid \frac{\varphi(m)}{p}$
$a^{\varphi(m) / p} \equiv a^{\text{gcd}(t, \varphi(m))} \equiv 1(\bmod m)$，与条件矛盾

原根个数
若一个数 $m$ 有原根，则它的原根个数为 $\varphi(\varphi(m))$

假设 $m$ 有原根 $g$，即 $\varphi(m) = \delta_m(g)$，根据性质 4
$\displaystyle \delta_m(g^k) = \frac{\delta_m(g)}{\text{gcd}(\delta_m(g), k)} = \frac{\varphi(m)}{\text{gcd}(\varphi(m), k)}$

如果有 $\text{gcd}(k, \varphi(m)) = 1$，那么有 $\delta_(g^k) = \varphi(m)$，即 $g^k$ 也是模 $m$ 的原根
满足 $\text{gcd}(\varphi(m), k) = 1$ 并且 $1 \leqslant k \leqslant \varphi(m)$ 的 $k$ 一共有 $\varphi(\varphi(m))$ 个

原根的判定，比如设 $m = 7$，求 $m = 7$ 的原根，只要根据判定定理，先算出 $\varphi(7) = 6$
然后素因子分解 $\varphi(7) = 6 = 2 \cdot 3$，如果 $a$ 是 $7$ 的原根，不妨设 $a = 3$
那么 $3^3 \equiv 6 \not \equiv 1 (\bmod \ 7)$，$3^2 \equiv 2 \not \equiv 1 (\bmod \ 7)$
所以 $3$ 是 $7$ 的一个原根

原根与简化剩余系
模 $m$ 的一个简化剩余系，是 $\varphi(m)$ 个整数的一个集合，这些数都对模 $m$ 互不同余，并且每一个数都和 $m$ 互素

如果 $\{a_1, a_2, \cdots, a_{\varphi(m)}\}$ 是模 $m$ 的一个简化剩余系，若 $(k, m) = 1$，那么
$(ka_1, ka_2, \cdots, ka_{\varphi(m)})$ 也是模 $m$ 的一个简化剩余系

原根与简化剩余系定理 令 $(a, m) = 1$，则 $a$ 是模 $m$ 的一个原根当且仅当
$\displaystyle \{a, a^2, \cdots, a^{\varphi(m)} \}$ 成为模 $m$ 的一个简化剩余系

必要性可以根据阶的性质1，直接得出
充分性，如果 $\{a, a^2, \cdots, a^{\varphi(m)}\}$ 是简化剩余系，那么 $(a, m) = 1$，又根据 Euler 定理
$a^{\varphi(m)} \equiv 1(\bmod \ m)$，并且这些数互不同余，所以 $\varphi(m)$ 是能够找到的最小的幂指 $k$
使得 $a^k \equiv 1(\bmod m)$，根据原根的定义，$a$ 是原根

原根存在定理
一个数 $m$ 存在原根，当且仅当 $m = 2, 4, p^{\alpha}, 2p^{\alpha}$，其中 $p$ 为奇素数，$\alpha \in \mathbb{N}^{*}$

下面分为四部分证明，分别是 $m = \{2, 4\}, \{p^{\alpha}\}, \{2p^{\alpha}\}, m \notin \{2, 4, p^{\alpha}, 2p^{\alpha}\}$

$m = 2, 4$，对于 $m = 2$，$1$ 是它的原根，对于 $m = 4$，$\varphi(4) = 2$，$3^{\varphi(4)/2} \equiv 3 \not \equiv 1 (\bmod 4)$，$3$ 是一个原根
或者可以用定义证明，$3^2 = 3^{\varphi(4)} \equiv 1 (\bmod 4)$，并且没有更小的幂指 $t$ 使得 $3^t \equiv 1(\bmod 4)$

以下用 $(a, p) = 1$ 表示 $a, p$ 互素

定理1，对于奇素数 $p$，$p$ 有原根
引理1，假设 $(a, p) = 1, (b, p) = 1$，存在 $c \in \mathbb{Z}$，使得 $\delta_p(c) = \text{lcm}(\delta_p(a), \delta_p(b))$
证明如下，先对 $\delta_m(a), \delta_m(b)$ 唯一分解，这里用 $m \leftarrow p$

$\displaystyle \delta_m(a) = \prod_{i = 1}^{k} p_i^{\alpha_i}, \quad \delta_m(b) = \prod_{i = 1}^{k} p_i^{\beta_i}$
令 $\displaystyle \delta_m(a) = XY, \ \delta_m(b) = ZW$，其中

$\displaystyle Y = \prod_{i = 1}^{k} p_i^{[\alpha_i > \beta_i] \alpha_i}, \quad X = \frac{\delta_m(a)}{Y}$

$\displaystyle W = \prod_{i = 1}^{k} p_i^{[\alpha_i \leqslant \beta_i] \beta_i}, \quad Z = \frac{\delta_m(b)}{W}$

通俗一点说，我们把 $\delta_m(a), \delta_m(b)$ 出现的所有素因子统计出来 $\{p_1, p_2, \cdots, p_k\}$
对于每一个素因子 $p_i$，如果它在 $\delta_m(a)$ 中出现的幂指比 $\delta_m(b)$ 中的大，就把它放到 $Y$ 中，否则放到 $W$ 中
如果因子 $p_i$ 在 $\delta_m(a)$ 中没有出现，它的幂指看作是 $0$
这样显然有 $\text{gcd}(Y, W) = 1$，$\text{lcm}(\delta_m(a), \delta_m(b)) = \text{lcm}(Y, W)$

根据阶的性质4， $\displaystyle \delta_m(a^{X}) = \frac{\delta_m(a)}{\text{gcd}(\delta_m(a), X)} = \frac{XY}{X} = Y$

同理，$\displaystyle \delta_m(b^Z) = W$，又因为 $(Y, W) = 1$，所以
$YW = \text{lcm}(Y, W) = \text{lcm} \left(\delta_m(a), \delta_m(b) \right)$

另一方面，$(a, m) = 1$，所以 $(a^k, m) = 1$，否则就可以找到 $p \mid a$，与 $(a, m) = 1$ 矛盾

根据阶的性质3，$\displaystyle \delta_m(a^Xb^Z) = \delta_m(a^X) \delta_m(b^Z) = YM = \text{lcm}(\delta_m(a), \delta_m(b))$
取 $c = a^Xb^Z$，证毕

接下来回到原问题
对于素数 $p$，$\{1, 2, \cdots, p-1\}$ 均与 $p$ 互素，对 $\varphi(p)$ 个数两两使用引理，我们可以找到一个 $g \in \mathbb{Z}$
使得 $\delta_p(g) = \textbf{lcm}(\delta_p(1), \delta_p(2), \cdots, \delta_p(p-1))$，说明对任意的 $j \in \{1, 2, \cdots, p-1\}$
有 $\delta_p(j) \mid \delta_p(g)$

研究二项同余式 $\displaystyle x^{\delta_p(g)} \equiv 1 (\bmod \ p)$
根据阶的性质2，对于二项同余式 $x^{\delta_p(g)} \equiv 1(\bmod \ p)$，有 $\delta_p(x) \mid \delta_p(g)$
也就是说，$x = j = \{1, 2, \cdots, p-1\}$ 都是同余式的根
根据拉格朗日定理，有 $p-1$ 个根，那么多项式的幂指 $\delta_p(g) \geqslant p-1$

再根据Fermat定理，$p$ 是素数并且 $p \nmid x$，那么 $x^{p-1} \equiv 1(\bmod \ p)$
满足 $p \nmid x$，也就是说 $(x \bmod p) \in \{1, 2, \cdots, p-1\}$，根据 $\bmod p$ 的余数进行分类
$x$ 可以有 $p-1$ 类取值，我们说同余方程 $x^{p-1} \equiv 1 (\bmod p)$ 有 $p-1$ 个根
回到本问题，用Fermat定理表述为，$\displaystyle x^{\delta_p(g)} \equiv 1(\bmod \ p)$
当 $\delta_p(g) = p-1$ 时恰有它全部的根，而本问题之前已经找出了 $\{1, 2, \cdots, p-1\}$ 个根
也许还有其他的根，所以 $\delta_p(g) \leqslant p-1$

综上所述，$\delta_p(g) = p-1 = \varphi(p)$，$g$ 为模 $p$ 的原根，证毕

定理2，对于奇素数 $p$，$\alpha \in \mathbb{N}^{*}$，$p^{\alpha}$ 有原根
证明的想法是，将模 $p$ 的原根平移
引理2，存在模 $p$ 的原根 $g$，使得 $g^{p-1} \not \equiv 1(\bmod \ p^2)$
证明，任取模 $p$ 的原根，如果发现 $g^{p-1} \equiv 1(\bmod p^2)$ 不满足条件，就让 $g = g+p$
$\{g, g^2, \cdots g^{\varphi(p)}\}$ 取遍 $p$ 的简化剩余系，同样 $\{g+p, \cdots, (g+p)^{\varphi(p)}\}$ 也取遍简化剩余系
因为 $(g+p)^k \equiv g(\bmod p)$，所以有 $(g+p)$ 也是模 $p$ 的原根

$\displaystyle (g+p)^{p-1} \equiv \binom{p-1}{0} g^{p-1} + \binom{p-1}{1} pg^{p-2}$
$\displaystyle \quad \equiv g^{p-1} + p(p-1)g^{p-2} \equiv 1-pg^{p-2} (\bmod p^2)$，因为 $pg^{p-2} \not \equiv 0 (\bmod p^2)$
所以有 $(g+p)^{p-1} \not \equiv 1(\bmod p^2)$

证明，如果 $g$ 是满足 $g^{p-1} \not \equiv 1(\bmod \ p^2)$ 的原根，那么对于任意 $\alpha \geqslant 1$，$g$ 也是模 $p^{\alpha}$ 的原根
假设 $t$ 是 $g$ 的阶 $(\bmod \ p^{\alpha})$，即令 $t = \delta_{p^{\alpha}}(g)$，我们希望证明 $t = \varphi(p^{\alpha})$
(1) 首先有 $g^t \equiv 1 (\bmod \ p^{\alpha})$，这是根据阶的定义
(2) 另外，$g^{t} = kp^{\alpha} + 1$，我们也有 $g^{t} \equiv 1(\bmod p)$
(3) $g^{\varphi(p)} \equiv 1 (\bmod p)$ 成立，$g^{k \varphi(p)} \equiv 1 (\bmod p)$ 恒成立，换句话说，$t = k \cdot \varphi(p)$
(4) 根据阶的性质2，因为 $t$ 是关于 $(\bmod p^{\alpha})$ 的阶，所以 $t \mid \varphi(p^{\alpha})$
综上所述，$k\varphi(p) \mid \varphi(p^{\alpha})$，但是 $\varphi(p^{\alpha}) = p^{\alpha - 1}(p-1), \ \varphi(p) = p-1$
(5) 可以推出 $k \mid p^{\alpha - 1}$，换句话说，$k = p^{\beta}, \ \beta \leqslant \alpha - 1$
这样，(3) 就可以写成 $t = p^{\beta}(p-1), \ \beta \leqslant \alpha - 1$
只需要证明 $\beta = \alpha - 1$ 即可，等价于对于 $\beta \leqslant \alpha - 2$，以下推出的一些结论都不成立
如果有 $\beta \leqslant \alpha - 2$，那么 $t = p^{\beta}(p-1) \mid p^{\alpha-2}(p-1) = \varphi(p^{\alpha - 1})$
如果假设成立，我们有 $\varphi(p^{\alpha - 1})$ 是 $t$ 的倍数，$t$ 又是 $g$ 的阶 $(\bmod p^{\alpha})$，所以有
$g^{\varphi(p^{\alpha - 1})} \equiv 1(\bmod \ p^{\alpha})$，接下来只要证明这个结论不成立即可

引理3，如果 $g$ 是模 $p$ 的一个原根使得 $g^{p-1} \not \equiv 1(\bmod \ p^2)$，那么对于 $\alpha \geqslant 2$，都有
$\displaystyle g^{\varphi \left(p^{\alpha - 1} \right)} \not \equiv 1(\bmod \ p^{\alpha})$
这里对 $\alpha$ 归纳，考虑 $(\bmod \ p^{\alpha+1})$ 时候的情形
显然 $\alpha = 2$ 时成立，先根据 Fermat-Euler 定理，有 $g^{\varphi \left(p^{\alpha - 1} \right)} \equiv 1 (\bmod \ p^{\alpha - 1})$ 恒成立
(1) 写成一般形式，$g^{\varphi \left(p^{\alpha - 1} \right)} = 1 + k p^{\alpha - 1}$，根据归纳，$\displaystyle g^{\varphi \left(p^{\alpha - 1} \right)} \not \equiv 1(\bmod \ p^{\alpha})$
可以推出 $p \nmid k$
(2) 将 (1) 中两边同时 $p$ 次方，$p \varphi(p^{\alpha - 1}) = \varphi(p^{\alpha})$，我们有

$\displaystyle g^{\varphi \left(p^{\alpha} \right)} = (1+kp^{\alpha - 1})^p = 1 + kp^{\alpha} + \binom{p}{2}k^2 p^{2(\alpha - 1)} + r p^{3(\alpha - 1)} + \cdots$

注意到 $\alpha \geqslant 2$，那么 $2\alpha - 1 \geqslant \alpha + 1, \ 3\alpha - 3 \geqslant \alpha + 1$，往后的项 $p$ 的幂指都比 $\alpha + 1$ 大
$\displaystyle g^{\varphi \left(p^{\alpha} \right)} \equiv 1 + kp^{\alpha} (\bmod \ p^{\alpha + 1})$
因为 $p \nmid k$，所以 $kp^{\alpha} \not \equiv 0 (\bmod p^{\alpha + 1})$，从而 $\displaystyle g^{\varphi(p^{\alpha})} \not \equiv 1(\bmod \ p^{\alpha +1})$，归纳成立

模 $p^{\alpha}$ 原根存在定理
如果 $g$ 是模 $p$ 的一个原根，那么对于所有 $\alpha \geqslant 1$，$g$ 也是模 $p^{\alpha}$ 的原根当且仅当 $g^{p-1} \not \equiv 1(\bmod \ p^2)$

模 $2p^{\alpha}$ 原根存在定理
如果 $p$ 是一个奇素数并且 $\alpha \geqslant 1$，那么存在模 $p^{\alpha}$ 的一个奇数原根 $g$
并且每一个这样的 $g$ 也是模 $2p^{\alpha}$ 的原根

(1) 如果 $g$ 是模 $p^{\alpha}$ 的一个原根，那么 $g + p^{\alpha}$ 也是模 $p^{\alpha}$ 的一个原根
但是 $g, g+p^{\alpha}$ 其中一个一定是奇数，所以模 $p^{\alpha}$ 的奇数原根总是存在的
(2) 不妨设模 $p^{\alpha}$ 的一个奇数原根是 $g$，并且 $g$ 的阶是 $f \ (\bmod \ 2p^{\alpha})$ （关于模 $(2p^{\alpha})$ 的阶）
我们只需要证明 $f = \varphi(2p^{\alpha})$
(3) 首先根据阶的性质，有 $f \mid \varphi(2p^{\alpha})$，根据不完全积性，$\varphi(2p^{\alpha}) = \varphi(2) \varphi(p^{\alpha}) = \varphi(p^{\alpha})$
首先有 $f \mid \varphi(p^{\alpha})$
(4) 另一方面，根据阶的定义，$g^{f} \equiv 1 (\bmod \ 2p^{\alpha})$，又可以推出 $g^{f} \equiv 1 (\bmod \ p^{\alpha})$
$g$ 首先是模 $p^{\alpha}$ 的一个原根，所以 $g^{\varphi(p^{\alpha})} \equiv 1 (\bmod \ p^{\alpha})$，从而 $\varphi(p^{\alpha}) \mid f$
综上所述，$f = \varphi(p^{\alpha}) = \varphi(2p^{\alpha})$

其他情况原根不存在
原根不存在定理 给定 $m\geqslant 1$，$m$ 的形式不是 $\{1, 2, 4, p^{\alpha}, 2p^{\alpha}\}$，其中 $p$ 是一个奇素数
则对于任意一个满足 $(a, m) = 1$ 的 $a$，我们有 $\displaystyle a^{\frac{ \varphi(m) } {2}} \equiv 1 (\bmod \ m)$
$m$ 没有原根

先来证明 $\alpha \geqslant 3$ 时，模 $2^{\alpha}$ 没有原根，只要证明 $\displaystyle x^{\varphi(2^{\alpha}) / 2} \equiv 1 (\bmod \ 2^{\alpha}), x$ 为奇数
也就是 $\varphi(8) = 2^3 - 2^2 = 4$，$x^2 \equiv 1 (\bmod \ 8)$，这是成立的，因为 $(2k + 1)^2 = 4k(k+1) + 1$
而 $k(k+1)$ 一定是偶数，所以 $x^2 = (2k+1)^2 \equiv 1 (\bmod 8)$

解下来对 $\alpha$ 归纳，归纳假设有 $\displaystyle f(x) = x^{\varphi(2^{\alpha})} = (1+2^{\alpha}\cdot t)^2 = 1 + 2^{\alpha+1}t + 2^{2\alpha}t^2$
因为 $2\alpha \geqslant \alpha + 1$，所以 $f(x) \equiv 1 (\bmod 2^{\alpha+1})$，而 $x^{\varphi(2^{\alpha})} = x^{\varphi(2^{\alpha + 1}) / 2}$，归纳假设成立

接下来考虑一般情况，设 $\displaystyle m = 2^{\alpha} p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_s^{\alpha_s}$

根据条件，$s = 1$ 时，$\displaystyle \alpha \geqslant 2$，另外 $\alpha = \{0, 1\}$ 时，$s \geqslant 2$
$\displaystyle \varphi(m) = \varphi(2^{\alpha}) \varphi(p_1^{\alpha_1}) \varphi(p_2^{\alpha_2}) \cdots \varphi(p_s^{\alpha_s})$

我们希望证明 对于 $(a, m) = 1$，有 $\displaystyle a^{\varphi(m) / 2} \equiv 1 (\bmod m)$

考虑模 $p_1^{\alpha_1}$，取其原根 $g$，即 $g^{\varphi(p_1^{\alpha_1})} \equiv 1(\bmod \ p_1^{\alpha_1})$
因为 $g$ 是原根，$\left<g, g^2, \cdots, g^{\varphi(p_1^{\alpha_1})} \right>$ 取遍 $p_1^{\alpha_1}$ 的简化剩余系
所以存在 $g^{k} \equiv a (\bmod p_1^{\alpha_1}), \quad (1 \leqslant a \leqslant p_1^{\alpha_1} - 1)$

$\displaystyle a^{\varphi(m) / 2} \equiv g^{k\varphi(m) / 2} \equiv g^{t\varphi(p_1^{\alpha_1})} (\bmod \ p_1^{\alpha_1})$

其中 $\displaystyle t = k \varphi(2^{\alpha}) \varphi(p_1^{\alpha_1}) \varphi(p_2^{\alpha_2}) \cdots \frac{\varphi(p_s^{\alpha_s}) } {2}$

如果 $\alpha \geqslant 2$，那么 $\varphi(2^{\alpha})$ 是偶数，$t \in \mathbb{Z}$
如果 $\alpha = \{0, 1\}$，那么 $s \geqslant 2$，$\varphi(p_2^{\alpha_2})$ 是偶数，$t \in \mathbb{Z}$

所以可以得到 $g^{t \cdot \varphi(p_1^{\alpha_1})} \equiv 1(\bmod p_1^{\alpha_1})$，因为 $g$ 是原根
对其他 $p_i$ 同理，所以有 $\displaystyle a^{\varphi(m)/2} \equiv 1 (\bmod \ p_i^{\alpha_i})$

下面只需要证明这个同余式对模 $2^{\alpha}$ 成立即可，因为要求 $(a, m) = 1$，所以对模 $2^{\alpha}$，要求 $a$ 为奇数
$\displaystyle a^{\varphi(2^{\alpha})} \equiv 1(\bmod \ 2^{\alpha})$，这个在第一种情况时候已经证明过了，要求 $\alpha \geqslant 3$
又因为 $\varphi(2^{\alpha}) \mid \varphi(m)$，所以 $a^{\varphi(m) / 2} \equiv 1 (\bmod \ 2^{\alpha})$，此时 $\alpha \geqslant 3$
若 $\alpha \leqslant 2$，我们有 $s \geqslant 1$，所以此时 $\varphi(m) = \varphi(2^{\alpha})\varphi(p_1^{\alpha_1}) \cdots \varphi(p_s^{\alpha_s}) = 2k \cdot \varphi(2^{\alpha})$
此时仍然有 $\varphi(2^{\alpha}) \mid \varphi(m) / 2$

综上所述，将结果全部乘起来，证明完毕

比赛杂题

Educational Codeforces Round 123 (Rated for Div. 2)
C.Increase Subarray Sums

题目大意，给定一个数组 $\left<a \right>$，$f(k)$ 表示你可以在数组 $a$ 中任意取 $k$ 个不同位置，把这些位置上的数都加上 $x$
修改完成后，$\left<a \right>$ 中连续一段和的最大值记为 $f(k)$
输出 $\left< f(0), f(1), \cdots, f(n) \right>$，注意长度为 $0$ 的子数组也算一部分

根据数据范围，$O(n^2)$ 复杂度的算法就可以通过

• 先预处理出长度为 $len = [1, 2, \cdots, n]$ 的连续子段，它们的和的最大值，记为 $\text{maxsum}(len)$
• 然后考虑修改 $i$ 个数，$i \in [0\cdots n]$，记修改 $i$ 个数得到的最大子段和为 $\text{ans}(i)$
  有 $2$ 种情况，第一种，有一个很长的段 $(len > i)$，它的子段和很大，那么我们肯定要从 $len$ 个数中，随便选 $i$ 个修改
  修改后的最大子段和，就是 $\text{maxsum}(len) + i \cdot x$
  第二种就是，有可能最大子段和，出现在很小的一段 $(len < i)$ 中，那么这 $len$ 个数，肯定是需要修改的
  最大子段和为 $S = \text{maxsum}(len) + len \cdot x$，还需要修改 $i - len$ 个数，怎么办
  实际上这剩下的 $i - len$ 个数可以在其他位置任意修改，不影响已经得到的最大子段和 $S$
• 因为长度为 $len$ 的段 $[l, r]$ 已经是原来的最大子段和了，如果 $len < i$，那么你选 $i$ 个数都增加 $x$
  相当于在原来的图像上，这些数同时往上平移 $x$，$[l, r]$ 仍然还是最大值

综上所述，我们只要枚举要修改的个数 $i \in \left<0, 1, \cdots n \right>$，同时枚举可能取到最大子段和的区间长度
$\text{len} \in [1, n]$，$\text{ans}(i) = \max(\text{maxsum}(len) + x \cdot \min(i, len))$

D. Cross Coloring

题目大意，给你一个 $n \times m$ 的棋盘，$q$ 次操作，每次给你 $(x, y)$，你可以把 $x$ 行 $y$ 列都染上 $k$ 种颜色中的任何一种
每一次染色，都会覆盖之前的颜色，问 $q$ 次操作之后，最终在棋盘中，有几种不同的颜色

这种问题，首先考虑什么时候，存在某一个格子 $(a, b)$，它能够被染上 $[1\cdots k]$ 中任意一种颜色，即 $\displaystyle \binom{k}{1}$ 种
满足这种条件的格子，可以把它看成是自由的

自由格子 $(a, b)$ 出现的充要条件如下
假设 $(a, b)$ 在第 $i$ 次第一次被染色，那么它在之后的 $[i+1\cdots n]$ 次染色中，都不会被覆盖
换句话说，如果第 $i$ 次染色，存在至少一个自由格子，那么答案 $\displaystyle ans \leftarrow ans \cdot \binom{k}{1}$

直接做比较麻烦，先考虑简单情况，对于最后一次操作，即第 $q$ 次，它可以选 $\displaystyle\binom{k}{1}$ 的任意一种颜色
这些颜色都会出现在棋盘上，有 $k$ 种，接下来考虑第 $q-1$ 次操作
$q-1$ 次操作染色的格子中，与第 $q$ 次操作重合的那些格子，不需要重复统计
其他格子呢？同样可以选 $\displaystyle\binom{k}{1}$ 的任意一种

经过这样分析，我们可以从 $i \in [q\to 1]$ 反着来遍历
每一次操作的时候，都标记一下它覆盖了哪些格子，不妨设当前进行第 $i$ 次操作
第 $i$ 次染色 $x$ 行 $y$ 列的时候，对于之前的 $[i+1, i+2, \cdots q]$ 操作已经标记过的格子，我们不做统计
如果能找到一个未标记的格子，那么它可以涂 $\displaystyle \binom{k}{1}$ 的任意一种颜色
将其统计到答案中，$\displaystyle ans \leftarrow ans \cdot \binom{k}{1}$

算法实现就比较简单了，假设第 $i$ 次操作 $(x, y)$，如果 $x$ 行之前没有操作过
并且至少存在一列未被标记，或者对称地， $y$ 列没有被操作过，至少存在一行未被标记，那么就对答案有 $\displaystyle \binom{k}{1}$ 的贡献