数学知识：欧拉函数，快速幂，扩展欧几里得，线性同余方程 讲解

下面是针对欧拉函数、快速幂、扩展欧几里得、线性同余方程这四个数学知识点的系统讲解，尽量清晰、通俗、带例子和核心代码（C++风格，便于竞赛使用）。

1. 欧拉函数 φ(n)

定义
φ(n) = 1 到 n 中与 n 互质的整数个数（包括 1）
（互质：gcd(x, n) = 1）

常见值（背下来）

• φ(1) = 1
• p 是质数 → φ(p) = p−1
• p 是质数 → φ(p^k) = p^k − p^(k−1) = p^(k−1) × (p−1)
• 如果 n = p1^k1 × p2^k2 × … × pr^kr （标准分解）
  则 φ(n) = n × (1−1/p1) × (1−1/p2) × … × (1−1/pr)

性质

• 积性函数：若 gcd(a,b)=1，则 φ(a×b) = φ(a)×φ(b)
• ∑_{d|n} φ(d) = n （非常重要！很多题会用到）

怎么快速求 φ(n)？

方法1：直接分解质因数（最常用）

long long euler_phi(long long n) {
    long long res = n;
    for (long long i = 2; i * i <= n; ++i) {
        if (n % i == 0) {           // 发现一个质因子
            res = res / i * (i - 1); // 乘 (1-1/p)
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) res = res / n * (n - 1); // 最后一个大质数
    return res;
}

方法2：线性筛预处理 1~N 所有 φ 值（N≤10^7 时常用）

const int N = 10000010;
int phi[N];
bool is_composite[N];
vector<int> primes;

void sieve_phi(int n) {
    for (int i = 1; i <= n; ++i) phi[i] = i;
    for (int i = 2; i <= n; ++i) {
        if (!is_composite[i]) {
            primes.push_back(i);
            phi[i] = i - 1;
        }
        for (int p : primes) {
            if (i * 1ll * p > n) break;
            is_composite[i * p] = true;
            if (i % p == 0) {
                phi[i * p] = phi[i] * p;
                break;
            } else {
                phi[i * p] = phi[i] * (p - 1);
            }
        }
    }
}

2. 快速幂（模意义下）

核心思想：把指数按二进制拆分，减少乘法次数
时间复杂度：O(log n)

普通写法（迭代版，最推荐）

// 计算 a^b % mod
long long qpow(long long a, long long b, long long mod) {
    long long res = 1;
    a %= mod;

    while (b > 0) {
        if (b & 1)          // 当前位是1
            res = res * a % mod;
        a = a * a % mod;    // 平方
        b >>= 1;            // 右移
    }
    return res;
}

例子
求 3^100000000000 % 1000000007

普通方法要乘 10^11 次 → 超时
快速幂只要 log(10^11) ≈ 37 次乘法

注意事项

• 乘法前一定要 % mod（防止溢出）
• 更安全写法：用 __int128 或 mulmod

// 防溢出版本（常用在 mod ≈ 1e9+7）
using ll = long long;
ll mul(ll a, ll b, ll mod) {
    return (a * (__int128)b) % mod;
    // 或使用 __int128 写法
}

3. 扩展欧几里得算法（exgcd）

目标：给定 a、b，求
ax + by = gcd(a,b) 的一组整数解 (x,y)

核心递推

// 返回 gcd，同时通过引用修改 x,y
long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    long long d = exgcd(b, a % b, y, x);  // 注意 x,y 交换
    y -= a / b * x;                       // 回代
    return d;
}

使用示例

ll x, y;
ll d = exgcd(240, 46, x, y);
cout << "gcd = " << d << "\n";
cout << "240x + 46y = " << d << " → x=" << x << ", y=" << y << "\n";

输出示例：

gcd = 2
240x + 46y = 2 → x= -9, y=47
验证：240×(-9) + 46×47 = -2160 + 2162 = 2 ✓

4. 线性同余方程 ax ≡ b (mod m)

求解 ax ≡ b (mod m)

有解条件：d = gcd(a, m) 必须整除 b

解的个数：如果有解，则有 d 个解（模 m 意义下）

求解步骤

1. 用 exgcd 求 d = gcd(a, m)，以及 ax’ + my’ = d
2. 如果 d 不整除 b → 无解
3. 否则，令 x0 = x’ × (b/d) （这是缩小后的解）
4. 则原方程的一个解是 x0
5. 全部解：x = x0 + k × (m/d) (k ∈ Z)，模 m 意义下有 d 组解

代码实现

// 返回解的个数，ans[0..cnt-1] 存放最小非负解
int linear_congruence(ll a, ll b, ll m, vector<ll>& ans) {
    ll x, y;
    ll d = exgcd(a, m, x, y);
    if (b % d != 0) return 0;   // 无解

    ans.clear();
    ll mod = m / d;             // 步长
    ll x0 = x * (b / d) % mod;  // 一个特解（可能负）
    x0 = (x0 % mod + mod) % mod;// 变成 [0, mod)

    for (ll k = 0; k < d; ++k) {
        ans.push_back( (x0 + k * mod) % m );
    }
    return d;
}

例子
求解 6x ≡ 9 (mod 15)

gcd(6,15)=3，3|9 → 有解，3 个解

用 exgcd 得到 6x + 15y = 3 的一个解 → x= -2, y=1
缩小：x0 = -2 × (9/3) = -6
x0 ≡ -6 (mod 15/3=5) → x0 ≡ 4 (mod 5)
通解：x ≡ 4, 9, 14 (mod 15)

总结口诀

• 欧拉函数 → 互质个数 + 乘法逆元基础
• 快速幂 → 所有模意义下大指数幂必备
• exgcd → 解贝祖等式 + 求逆元 + 解线性同余
• 线性同余 → gcd 整除 b → d 个解，步长 m/d

如果你有具体题目想分析（比如求逆元、求 φ 的前缀和、解同余方程组等），可以直接贴出来，我带你一步步推！