【算法基础篇】（四十四）数论之欧拉定理与扩展欧拉定理深度解析：从降幂到超大规模幂运算

#include <iostream>
using namespace std;

typedef long long LL;

// 试除法计算单个数字的欧拉函数
LL get_phi(LL x) {
    LL ret = x;
    // 枚举质因子，直到 sqrt(x)
    for (LL i = 2; i <= x / i; ++i) {
        if (x % i == 0) {
            // 应用公式：ret = ret * (i-1) / i
            ret = ret / i * (i - 1);
            // 除尽所有i的倍数，避免重复计算
            while (x % i == 0) {
                x /= i;
            }
        }
    }
    // 剩余x>1，说明是最后一个质因子
    if (x > 1) {
        ret = ret / x * (x - 1);
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    LL m;
    cin >> m;
    cout << "φ(" << m << ") = " << get_phi(m) << endl;
    return 0;
}

#include <iostream>
using namespace std;

typedef long long LL;

// 快速幂计算 (a^b) mod p
LL qpow(LL a, LL b, LL p) {
    LL ret = 1;
    a = a % p;  // 先对底数取模，防止溢出
    while (b > 0) {
        // 若当前二进制位为1，将结果乘上当前底数的幂次
        if (b & 1) {
            ret = ret * a % p;  // 边乘边取模，避免溢出
        }
        // 底数平方，对应二进制位左移一位
        a = a * a % p;
        // 指数右移一位，处理下一个二进制位
        b >>= 1;
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    LL a = 2, b = 10, p = 4;
    cout << (a ^ b) << " mod " << p << " = " << qpow(a, b, p) << endl;
    return 0;
}

#include <iostream>
#include <string>
using namespace std;

typedef long long LL;

// 试除法计算单个数字的欧拉函数
LL get_phi(LL x) {
    LL ret = x;
    for (LL i = 2; i <= x / i; ++i) {
        if (x % i == 0) {
            ret = ret / i * (i - 1);
            while (x % i == 0) {
                x /= i;
            }
        }
    }
    if (x > 1) {
        ret = ret / x * (x - 1);
    }
    return ret;
}

// 处理大指数b（字符串形式），返回b mod phi + (b >= phi ? phi : 0)
LL process_b(const string& s, LL phi) {
    LL t = 0;
    bool flag = false;  // 标记b是否 >= phi
    for (char ch : s) {
        t = t * 10 + (ch - '0');
        if (t >= phi) {
            flag = true;
            t %= phi;  // 边计算边取模，避免溢出
        }
    }
    if (flag) {
        t += phi;  // 满足b >= phi，加上phi
    }
    return t;
}

// 快速幂计算 (a^b) mod p
LL qpow(LL a, LL b, LL p) {
    LL ret = 1;
    a = a % p;
    while (b > 0) {
        if (b & 1) {
            ret = ret * a % p;
        }
        a = a * a % p;
        b >>= 1;
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    LL a, m;
    string s;
    cin >> a >> m >> s;
    
    if (m == 1) {  // 特殊情况：mod 1 结果恒为0
        cout << 0 << endl;
        return 0;
    }
    
    LL phi = get_phi(m);
    LL b = process_b(s, phi);
    LL ans = qpow(a, b, m);
    cout << ans << endl;
    
    return 0;
}

#include <iostream>
#include <cstring>
using namespace std;

typedef long long LL;
const int MAXN = 1e7 + 10;

bool st[MAXN];       // 标记是否为合数
int primes[MAXN], cnt;  // 存储质数
int phi[MAXN];       // 存储欧拉函数值

// 线性筛（欧拉筛）预处理1~MAXN的欧拉函数
void pre_phi() {
    memset(st, false, sizeof st);
    memset(phi, 0, sizeof phi);
    cnt = 0;
    phi[1] = 1;
    for (int i = 2; i <= MAXN; ++i) {
        if (!st[i]) {  // i是质数
            primes[++cnt] = i;
            phi[i] = i - 1;
        }
        // 枚举所有已找到的质数，筛掉i*primes[j]
        for (int j = 1; 1LL * i * primes[j] <= MAXN; ++j) {
            int x = i * primes[j];
            st[x] = true;
            if (i % primes[j] == 0) {  // primes[j]是i的最小质因子
                phi[x] = phi[i] * primes[j];
                break;
            } else {  // primes[j]不是i的质因子，i与primes[j]互质
                phi[x] = phi[i] * (primes[j] - 1);
            }
        }
    }
}

// 快速幂计算 (a^b) mod p
LL qpow(LL a, LL b, LL p) {
    LL ret = 1;
    a = a % p;
    while (b > 0) {
        if (b & 1) {
            ret = ret * a % p;
        }
        a = a * a % p;
        b >>= 1;
    }
    return ret;
}

// 递归计算稳定后的结果
int dfs(int p) {
    if (p == 1) {
        return 0;
    }
    // 递归应用扩展欧拉定理
    return qpow(2, dfs(phi[p]) + phi[p], p);
}

int main() {
    pre_phi();  // 预处理欧拉函数
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        int p;
        cin >> p;
        cout << dfs(p) << endl;
    }
    return 0;
}