【模板】扩展欧拉定理

1 扩展欧拉定理公式

对于任意正整数 $a, m$ ，定义 $\varphi(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, b < \varphi(m) \\ a^{(b \bmod \varphi(m)) + \varphi(m)} \pmod m & \gcd(a, m) \neq 1, b \ge \varphi(m) \end{cases}

在竞赛编程中的通用写法： 通常我们不需要特判 $\gcd(a, m)$ 是否为 1。只要 $b \ge \varphi(m)$ ，无论是哪种情况，统一使用第三个公式 $a^{(b \bmod \varphi(m)) + \varphi(m)} \pmod m$ 都是正确的（对于互质的情况，加 $\varphi(m)$ 只是多乘了一轮循环，结果不变）。

2 解题思路

求欧拉函数 $\varphi(m)$ ：由于 $m \le 10^8$ ，直接用 $O(\sqrt{m})$ 的试除法求 $\varphi(m)$ 即可。
处理超大指数 $b$ （欧拉降幂）：
- $b$ 是以字符串形式输入的。
- 我们在读入 $b$ 的每一个数字时，按照十进制进位逻辑计算 $b \bmod \varphi(m)$ 。
- 关键点：我们需要判断原始的 $b$ 是否大于等于 $\varphi(m)$ 。
  - 如果 $b < \varphi(m)$ ，指数就是 $b$ 。
  - 如果 $b \ge \varphi(m)$ ，指数变为 $(b \bmod \varphi(m)) + \varphi(m)$ 。
快速幂：利用降幂后的指数，计算 $a^{\text{new\_exp}} \bmod m$ 。

3 C++ 代码实现

cpp

#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

typedef long long ll;

ll a, m; // a是底数, m是模数

// 1. 求欧拉函数 phi(n)
ll get_phi(ll n) {
    ll res = n;
    for (ll i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            res = res / i * (i - 1);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) res = res / n * (n - 1);
    return res;
}

// 2. 快速幂
ll qpow(ll base, ll exp, ll mod) {
    ll res = 1;
    while (exp > 0) {
        if (exp & 1) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

// 3. 处理大数 b 的读入与降幂
// 返回降幂后的指数
ll read_b_and_reduce(ll phi_m) {
    ll val = 0;
    bool flag = false; // 标记 b 是否大于等于 phi_m
    int ch = getchar();
    
    // 跳过非数字字符（比如空格）
    while (ch < '0' || ch > '9') ch = getchar();
    
    // 边读边取模
    while (ch >= '0' && ch <= '9') {
        val = val * 10 + (ch - '0');
        if (val >= phi_m) {
            flag = true;
            val %= phi_m;
        }
        ch = getchar();
    }
    
    // 应用扩展欧拉定理公式
    if (flag) {
        return val + phi_m;
    } else {
        return val;
    }
}

int main() {
    // 题目输入格式：a m b
    // 注意：b 是第三个参数，且是超大数
    cin >> a >> m;

    ll phi_m = get_phi(m);
    
    // 读取 b 并根据扩展欧拉定理进行降幂
    ll final_exp = read_b_and_reduce(phi_m);

    // 计算最终答案
    printf("%lld\n", qpow(a, final_exp, m));

    return 0;
}

4 代码细节解析

read_b_and_reduce 函数：这是解题的核心。普通的快读（Fast I/O）只是返回 val % mod，但扩展欧拉定理要求当 $b \ge \varphi(m)$ 时，要在取模结果上加回 $\varphi(m)$ 。
- 代码中使用 flag 变量来检测是否发生过取模或者值已经超过了 $\varphi(m)$ 。一旦 flag 为真，最终返回 val + phi_m。
输入顺序：题目给出的样例和说明是 $a, m, b$ 。代码中先 cin >> a >> m，然后调用 read_b_and_reduce 处理紧随其后的 $b$ 。
数据范围：虽然计算过程中取模了，但中间乘法 val * 10 或者 res * base 可能会溢出 int，所以全程使用 long long 是安全的。

5 复杂度分析

求欧拉函数： $O(\sqrt{m})$ 。由于 $m \le 10^8$ ，计算量约为 $10^4$ ，非常快。
读取 $b$ ： $O(\text{len}(b))$ 。即 $b$ 的位数，题目最大为 $2 \times 10^7$ 位，线性扫描一遍即可。
快速幂： $O(\log(\varphi(m)))$ 。
总时间复杂度：主要瓶颈在读取 $b$ 的字符串处理上，但对于 $100\%$ 的数据完全可以通过。