核心逻辑与数学原理
1. 欧拉函数的数学性质
欧拉函数 $\\varphi(N)$ 表示满足 $1 \le i \le N$ 且 $\gcd(i, N) = 1$ 的整数 $i$ 的个数。除线性筛法递推外，它还具备以下数论核心性质：
- 性质 1：若 $p$ 为质数，则 $\varphi(p) = p - 1$；若 $k \ge 1$，则 $\varphi(p^k) = p^k - p^{k-1} = p^k \left(1 - \frac{1}{p}\right)$。
- 性质 2（狄利克雷卷积展开）：一个正整数 $N$ 的所有因子的欧拉函数之和等于它本身，即：
$$\sum_{d \mid N} \varphi(d) = N$$
- 性质 3：小于等于 $N$ 且与 $N$ 互质的所有数的代数和为：
$$S = \frac{N \cdot \varphi(N)}{2} \quad (N > 1)$$
2. 欧拉定理（Euler's Theorem）
若正整数 $a$ 与 $m$ 互质（即 $\gcd(a, m) = 1$），则有：
$$a^{\varphi(m)} \equiv 1 \pmod m$$
当 $m$ 为质数时，$\varphi(m) = m - 1$，定理退化为费马小定理：$a^{m-1} \equiv 1 \pmod m$。
3. 扩展欧拉定理（大数降幂公式）
在 NOIP 竞赛中，经常面对求 $a^b \bmod m$ 的场景，其中底数 $a$ 和模数 $m$ 在正常范围内，但指数 $b$ 极大（例如 $b \le 10^{2000000}$，以字符串形式给出）。由于不能直接对指数进行 $b \bmod m$ 操作（这是初学者最常犯的数学常识错误），必须使用扩展欧拉定理进行降幂拦截。
该定理不要求 $a$ 与 $m$ 互质，具有普适性： $$a^b \equiv \begin{cases} a^{b \bmod \varphi(m)} \pmod m & \gcd(a, m) = 1 \ a^b \pmod m & \gcd(a, m) \neq 1 \text{ 且 } b < \varphi(m) \ a^{(b \bmod \varphi(m)) + \varphi(m)} \pmod m & \gcd(a, m) \neq 1 \text{ 且 } b \ge \varphi(m) \end{cases}$$
状态设计与算法推导
单个大数降幂的读取状态设计
对于超长指数 $b$，我们无法将其存入任何原生整型。必须采用单字符流读入（快读变式）进行动态降幂。
在边读边转的过程中，我们需要维护两层状态：
- 数值维：当前的指数模 $\varphi(m)$ 的值。
- 状态维：当前的真实指数值是否已经超越了 $\varphi(m)$。
定义一个布尔标记 over_limit。设当前已读入的数字构成的数值为 $b'$，读入下一个数字 $d$ 时：
$$b_{\text{new}}' = b' \cdot 10 + d$$
若在某一时刻 $b_{\text{new}}' \ge \varphi(m)$，则令 over_limit = true，并强制执行：
$$b_{\text{new}}' = (b' \cdot 10 + d) \bmod \varphi(m)$$
最终，若 over_limit 为 true，则最终带入快速幂的指数为 $b' + \varphi(m)$；否则直接为 $b'$。由此实现了将 $O(10^{2000000})$ 规模的指数瞬间压缩至 $O(M)$ 级别。
C++ 标准源码
#include <iostream>
#include <string>
// 单点求解欧拉函数 phi(m)，时间复杂度 O(\sqrt{m})
long long get_phi(long long m) {
long long ans = m;
long long temp = m;
for (long long i = 2; i * i <= temp; ++i) {
if (temp % i == 0) {
ans = ans / i * (i - 1); // 先除后乘，杜绝截断与溢出
while (temp % i == 0) temp /= i;
}
}
if (temp > 1) {
ans = ans / temp * (temp - 1);
}
return ans;
}
// 带有模数基底的快速幂
long long quick_power(long long base, long long exp, long long mod) {
long long res = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) res = (__int128_t)res * base % mod; // __int128_t 严防乘法中途越界
base = (__int128_t)base * base % mod;
exp >>= 1;
}
return res;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
long long a, m;
if (std::cin >> a >> m) {
long long phi_m = get_phi(m);
long long b = 0;
bool over_limit = false;
char ch;
// 过滤前导非数字字符
while (std::cin >> ch && (ch < '0' || ch > '9'));
// 动态读入大数并执行扩展欧几里得降幂判定
while (ch >= '0' && ch <= '9') {
b = b * 10 + (ch - '0');
if (b >= phi_m) {
over_limit = true;
b %= phi_m;
}
// 尝试读取下一个字符，若非数字则安全终止
if (!(std::cin >> ch)) break;
}
// 根据定理边界条件组装最终的指数状态
long long final_exp = b;
if (over_limit) {
final_exp += phi_m;
}
long long ans = quick_power(a, final_exp, m);
std::cout << ans << "\n";
}
return 0;
}NOIP 实战避坑指南
- 指数大数读入时错套传统模运算
部分选手在读入超大指数 $b$ 时，顺手写了b = (b * 10 + ch - '0') % m。注意：指数必须模 $\varphi(m)$ 而不是模 $m$。一旦混淆，计算出的答案与正确结果将毫无关联。 - 忽略 $b < \varphi(m)$ 时的加法偏移破坏性质
扩展欧几里得定理明确指出，只有在 $b \ge \varphi(m)$ 时，指数才能套用 $b \bmod \varphi(m) + \varphi(m)$。如果 $b$ 本身很小（比如 $b = 1$），而你盲目加上了 $\varphi(m)$，当 $\gcd(a, m) \neq 1$ 时，算出来的结果会比原版多乘了若干个因子，导致逻辑溃败。必须使用over_limit标记严格分支。
经典 NOIP/洛谷 真题
1. 洛谷 P5091 【模板】扩展欧拉定理
- 题意描述：给定 $a, m$ 和一个长度达 $2 \times 10^6$ 的数字字符串 $b$，求 $a^b \pmod m$ 的值。
- 问题本质：大数降幂的极限模板落地。
- 核心解题思路：由于 $b$ 无法用普通的整形承载，直接使用标准源码中给出的高精流式读取算法。首先对 $m$ 进行 $O(\sqrt{m})$ 质因数分解求出 $\varphi(m)$，然后在读入字符串的过程中实施动态取模和边界标记。最终将收敛后的指数带入快速幂完成 $O(\log \varphi(m))$ 的计算。
2. 洛谷 P4139 上帝与集合的正确用法
- 题意描述：求解无限层幂塔的取模结果，即求 $2^{2^{2^{\dots}}} \pmod p$ 的值。多组询问， $p \le 10^7$。
- 问题本质：扩展欧拉定理的递归收敛性。
- 核心解题思路：根据扩展欧拉定理，设 $f(p) = 2^{2^{2^{\dots}}} \pmod p$。因为幂塔层数无限，它可以被视作以自己为指数的结构，即 $f(p) = 2^{f(\varphi(p)) + \varphi(p)} \pmod p$。由于任何正整数在连续求 $\varphi$ 的迭代下，其值会呈对数级别速度缩减，最多 $O(\log p)$ 次迭代后 $\varphi(p)$ 就会收敛为 $1$。一旦模数变为 $1$，任何数对其取模均为 $0$，递归触底。因此可通过预处理线性筛欧拉函数，再配合递归函数完成层层回溯计算。