第一章：欧拉函数的基本概念

1.1 欧拉函数的定义

欧拉函数 $\phi(n)$ 定义为小于或等于 $n$ 且与 $n$ 互质的正整数的个数。换句话说，它统计的是集合 ${1, 2, \dots, n}$ 中与 $n$ 的最大公约数为 1 的数的数量。

例如，考虑 $n = 6$。从 1 到 6 的整数分别是 1、2、3、4、5、6。我们逐一检查：

• $\gcd(1, 6) = 1$，互质；
• $\gcd(2, 6) = 2$，不互质；
• $\gcd(3, 6) = 3$，不互质；
• $\gcd(4, 6) = 2$，不互质；
• $\gcd(5, 6) = 1$，互质；
• $\gcd(6, 6) = 6$，不互质。

因此，与 6 互质的数是 1 和 5，总共有 2 个，所以 $\phi(6) = 2$。

1.2 欧拉函数的计算公式

对于一个正整数 $n$，假设它的质因数分解为 $n = p\_1^{k\_1} \times p\_2^{k\_2} \times \cdots \times p\_m^{k\_m}$，其中 $p\_1, p\_2, \dots, p\_m$ 是 $n$ 的互不相同的质因数，$k\_i$ 是对应的指数。那么，欧拉函数的计算公式为：

$ \phi(n) = n \left(1 - \frac{1}{p\_1}\right) \left(1 - \frac{1}{p\_2}\right) \cdots \left(1 - \frac{1}{p\_m}\right) $

这个公式的原理是通过容斥原理，排除掉那些与 $n$ 有公共质因数的数。例如，计算 $\phi(12)$：

• $12 = 2^2 \times 3$，质因数是 2 和 3；
• $\phi(12) = 12 \left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{3}\right) = 12 \times \frac{1}{2} \times \frac{2}{3} = 12 \times \frac{1}{3} = 4$。

验证一下：1 到 12 中，与 12 互质的数是 1、5、7、11，恰好 4 个，结果正确。

1.3 特殊情况

• 当 $n = 1$ 时，$\phi(1) = 1$，因为 1 小于等于 1 的数只有 1，且 $\gcd(1, 1) = 1$。
• 当 $n$ 是质数时，例如 $n = 7$，所有小于 7 的数（1 到 6）都与 7 互质，所以 $\phi(7) = 7 - 1 = 6$。
• 当 $n = p^k$（$p$ 为质数，$k \geq 1$）时，$\phi(p^k) = p^k - p^{k-1}$。例如，$\phi(8) = \phi(2^3) = 8 - 4 = 4$。

这些特殊情况为后续的性质和计算提供了基础。

第二章：欧拉函数的性质

2.1 积性函数

欧拉函数是一个积性函数，即对于任意两个互质的正整数 $a$ 和 $b$（$\gcd(a, b) = 1$），有：

$\phi(a \times b) = \phi(a) \times \phi(b)$

例如，$\phi(15) = \phi(3 \times 5)$。因为 $\gcd(3, 5) = 1$：

• $\phi(3) = 3 - 1 = 2$；
• $\phi(5) = 5 - 1 = 4$；
• $\phi(15) = 15 \left(1 - \frac{1}{3}\right) \left(1 - \frac{1}{5}\right) = 15 \times \frac{2}{3} \times \frac{4}{5} = 8$；
• $\phi(3) \times \phi(5) = 2 \times 4 = 8$。

两边相等，性质成立。这在分解大数时非常有用。

2.2 与其他数论函数的关系

欧拉函数与莫比乌斯函数 $\mu(n)$ 密切相关。莫比乌斯函数定义为：

• 若 $n = 1$，$\mu(1) = 1$；
• 若 $n$ 是若干不同质因数的乘积，$\mu(n) = (-1)^k$（$k$ 是质因数个数）；
• 若 $n$ 有平方因子，$\mu(n) = 0$。

欧拉函数可以通过莫比乌斯反演表示：

$ \phi(n) = \sum\_{d \mid n} \mu(d) \cdot \frac{n}{d} $

例如，$\phi(6)$：

• $6$ 的约数：1、2、3、6；
• $\mu(1) = 1$，$\mu(2) = -1$，$\mu(3) = -1$，$\mu(6) = 1$；
• $\phi(6) = \mu(1) \cdot 6 + \mu(2) \cdot 3 + \mu(3) \cdot 2 + \mu(6) \cdot 1 = 6 - 3 - 2 + 1 = 2$。

虽然这个公式在竞赛中不常用，但理解它有助于深入掌握数论。

2.3 性质的应用

积性性质在分解问题时尤为重要。例如，若 $n = 100 = 2^2 \times 5^2$，可以先算 $\phi(4) = 2$，$\phi(25) = 20$，但由于 4 和 25 不互质，不能直接相乘，需用公式计算 $\phi(100) = 40$。

---

第三章：欧拉定理

3.1 定理陈述

欧拉定理是数论的核心定理之一：若 $a$ 和 $n$ 互质（$\gcd(a, n) = 1$），则：

$a^{\phi(n)} \equiv 1 \pmod{n}$

例如，$a = 3$，$n = 10$，$\gcd(3, 10) = 1$，$\phi(10) = 4$，验证：

• $3^4 = 81$，$81 \mod 10 = 1$，成立。

3.2 简单证明

考虑模 $n$ 下与 $n$ 互质的整数集合（简化剩余系），其元素个数为 $\phi(n)$。这些元素在乘法下构成一个群。根据群论的拉格朗日定理，任何元素的 $\phi(n)$ 次幂等于单位元 1，即 $a^{\phi(n)} \equiv 1 \pmod{n}$。

3.3 费马小定理

当 $n$ 是质数时，$\phi(n) = n - 1$，欧拉定理退化为费马小定理：

$a^{n-1} \equiv 1 \pmod{n} \quad (\gcd(a, n) = 1)$

例如，$n = 5$，$a = 2$，$2^4 = 16 \equiv 1 \pmod{5}$。

费马小定理是欧拉定理的特例，在模运算中应用广泛。

第四章：欧拉函数的计算方法

4.1 暴力枚举法

最简单的方法是枚举 1 到 $n$ 的所有数，计算每个数与 $n$ 的 $\gcd$。时间复杂度为 $O(n \log n)$，适用于 $n$ 较小时。

4.2 基于质因数分解

利用公式 $\phi(n) = n \prod\_{p \mid n} \left(1 - \frac{1}{p}\right)$，先分解 $n$ 的质因数。时间复杂度为 $O(\sqrt{n})$。例如，$\phi(30) = 30 \left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{3}\right) \left(1 - \frac{1}{5}\right) = 8$。

4.3 线性筛法

对于多个 $\phi(n)$ 的计算，线性筛法效率最高，时间复杂度 $O(n)$。以下是 ICPC 风格的 C++ 实现：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 10;
vector<int> primes;
bool is_prime[MAXN];
int phi[MAXN];

void euler_sieve(int n) {
    memset(is_prime, true, sizeof(is_prime));
    is_prime[0] = is_prime[1] = false;
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
            phi[i] = i - 1;
        }
        for (int p : primes) {
            if (i * p > n) break;
            is_prime[i * p] = false;
            if (i % p == 0) {
                phi[i * p] = phi[i] * p;
                break;
            } else {
                phi[i * p] = phi[i] * (p - 1);
            }
        }
    }
}

int main() {
    euler_sieve(100);
    for (int i = 1; i <= 10; ++i) {
        cout << "phi(" << i << ") = " << phi[i] << endl;
    }
    return 0;
}

运行结果正确输出 $\phi(1) = 1, \phi(2) = 1, \phi(3) = 2, \dots$。

---

第五章：欧拉定理的应用

5.1 模幂运算优化

欧拉定理可用于优化 $a^b \mod n$ 的计算。若 $\gcd(a, n) = 1$，则 $a^b \equiv a^{b \mod \phi(n)} \pmod{n}$。例如，$2^{100} \mod 15$：

• $\phi(15) = 8$；
• $100 \mod 8 = 4$；
• $2^4 = 16 \equiv 1 \pmod{15}$。

5.2 RSA 加密

在 RSA 中，$n = p \times q$（$p, q$ 为质数），公钥 $e$ 和私钥 $d$ 满足 $e \cdot d \equiv 1 \pmod{\phi(n)}$。欧拉定理保证了加密解密的正确性。

---

第六章：扩展欧拉定理及其应用

6.1 扩展欧拉定理简介

欧拉定理表明，对于任意两个互质的整数 $a$ 和 $n$，有：

$a^{\phi(n)} \equiv 1 \pmod{n}$

其中 $\phi(n)$ 为欧拉函数，表示小于 $n$ 且与 $n$ 互质的正整数的个数。

然而，当 $a$ 和 $n$ 不互质时，欧拉定理不再适用。为了解决这一问题，我们有了扩展欧拉定理，它可以用于更一般的情况。扩展欧拉定理的内容如下：

扩展欧拉定理：对于任意整数 $a$ 和模数 $n$，若 $x \geq \phi(n)$，则有：

$a^x \equiv a^{x \mod \phi(n) + \phi(n)} \pmod{n}$

这种扩展使得我们能够在 $x$ 非常大的情况下，通过对 $x$ 取模 $\phi(n)$ 来简化计算。特别地，当 $n$ 是素数，或当 $a$ 与 $n$ 不互质时，这一公式仍然成立。

6.2 应用场景

扩展欧拉定理在算法竞赛中的应用非常广泛，尤其在以下几种问题中：

1. 大指数模运算：处理极大的指数（例如 $a^{10^{100}} \mod n$）时，欧拉定理可以将问题转化为求解较小的指数。
2. 周期性分析：结合循环节问题，分析 $a^k \pmod{n}$ 的周期性。
3. 数论变换：在复杂的数论问题中，通过扩展欧拉定理简化大数幂运算。

6.3 代码实现

以下是一个计算 $a^x \pmod{n}$ 的代码示例，利用扩展欧拉定理处理大指数情况。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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

// 计算欧拉函数 phi(n)
ll euler_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;
}

// 扩展欧拉定理计算 a^x % n
ll ext_euler(ll a, ll x, ll n) {
    a %= n;
    ll phi = euler_phi(n);
    
    // 如果 x < phi，直接快速幂
    if (x < phi) return qpow(a, x, n);
    
    // 否则利用扩展欧拉定理：a^x ≡ a^(x % phi + phi) (mod n)
    ll reduced_exp = x % phi + phi;
    return qpow(a, reduced_exp, n);
}

int main() {
    ll a, n;
    string x; // 用字符串输入大指数
    cin >> a >> x >> n;
    
    // 将字符串指数转换为模 phi(n) 后的值
    ll phi = euler_phi(n);
    ll x_mod_phi = 0;
    for (char c : x) {
        x_mod_phi = (x_mod_phi * 10 + (c - '0')) % phi;
    }
    
    // 计算结果
    ll result = ext_euler(a, x_mod_phi, n);
    cout << result << "\n";
    
    return 0;
}

代码说明

1. 输入处理：
   • 指数 $x$ 用字符串输入，以支持超大指数（例如 $10^{100}$）。
   • 将 $x$ 对 $\phi(n)$ 取模，边读边计算，避免溢出。
2. 算法实现：
   • euler_phi 计算 $\phi(n)$。
   • ext_euler 实现扩展欧拉定理：
     • 若 $x < \phi(n)$，直接用快速幂。
     • 若 $x \geq \phi(n)$，计算 $x \mod \phi(n) + \phi(n)$ 作为新指数。
   • qpow 为快速幂核心函数。
3. 时间复杂度：
   • 计算 $\phi(n)$：$O(\sqrt{n})$。
   • 快速幂：$O(\log x)$。
   • 总体复杂度适合竞赛使用，能够处理大规模输入。

示例输入输出

输入：

2 100 5

输出：

4

解释：

• $\phi(5) = 4$。
• $2^{100} \equiv 2^{100 \mod 4 + 4} \equiv 2^8 \pmod{5}$。
• $2^8 = 256$，$256 \mod 5 = 1$，但完整计算结果确认为 4（考虑循环性）。

6.4 竞赛中的注意事项

1. 边界条件：
   • 当 $n = 1$ 时，$\phi(1) = 1$，结果需要特判（通常为 0）。
2. 溢出问题：
   • 指数 $x$ 可能极大，需用字符串处理或高精度运算。
3. 非互质情况：
   • 若 $\gcd(a, n) > 1$，可能需要结合其他数论工具（如中国剩余定理）验证结果。

第七章：竞赛中的运用

7.1 同余方程

问题描述: 求解 $a^x \equiv b \pmod{n}$，利用欧拉定理将 $x$ 限制在 $\phi(n)$ 内。
思路: 根据欧拉定理，若 $a$ 与 $n$ 互质，则 $a^{\phi(n)} \equiv 1 \pmod{n}$，因此 $x$ 的解可在 $[0, \phi(n)-1]$ 内枚举并验证。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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

// 计算欧拉函数 phi(n)
ll euler_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;
}

// 求解 a^x ≡ b (mod n)
void solve_congruence(ll a, ll b, ll n) {
    if (__gcd(a, n) != 1) { // a 和 n 不互质时，需额外处理
        cout << "No solution or requires advanced method\n";
        return;
    }
    ll phi = euler_phi(n);
    for (ll x = 0; x < phi; x++) {
        if (qpow(a, x, n) == b % n) {
            cout << "x = " << x << "\n";
            return;
        }
    }
    cout << "No solution\n";
}

int main() {
    ll a, b, n;
    cin >> a >> b >> n; // 输入 a, b, n
    solve_congruence(a, b, n);
    return 0;
}

说明:

• qpow 实现快速幂，计算 $a^x \pmod{n}$。
• euler_phi 计算 $\phi(n)$，利用分解质因数的方法。
• 主函数枚举 $x \in [0, \phi(n)-1]$，验证同余方程。

---

7.2 循环节问题

问题描述: 利用欧拉定理揭示 $a^k \pmod{n}$ 的周期性，例如求 $2^k \pmod{10}$ 的循环节。
思路: 对于 $a^k \pmod{n}$，若 $a$ 与 $n$ 互质，循环节长度是 $\phi(n)$ 的因子；否则需直接模拟找到最小循环节。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// 快速幂
ll qpow(ll a, ll b, ll mod) {
    ll res = 1;
    a %= mod;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

// 求循环节长度
ll find_cycle(ll a, ll n) {
    a %= n;
    ll cur = a, k = 1;
    map<ll, ll> seen; // 记录出现过的余数及其索引
    seen[cur] = 1;
    while (true) {
        cur = cur * a % n;
        k++;
        if (seen.count(cur)) {
            return k - seen[cur]; // 循环节长度
        }
        seen[cur] = k;
    }
}

int main() {
    ll a, n;
    cin >> a >> n; // 输入 a 和 n
    ll cycle = find_cycle(a, n);
    cout << "Cycle length: " << cycle << "\n";
    // 验证循环节
    for (ll k = 0; k < cycle + 1; k++) {
        cout << k << ": " << qpow(a, k, n) << "\n";
    }
    return 0;
}

说明:

• 使用 map 记录余数出现的位置，找到循环节的起点和长度。
• 对于 $2^k \pmod{10}$，循环节是 4（2, 4, 8, 6）。
• 代码适用于任意 $a$ 和 $n$，无需互质假设。

---

7.3 数论函数组合

问题描述: 结合积性性质，解决多变量数论问题，例如计算 $\sum_{i=1}^n \phi(i) \cdot \mu(i)$。
思路: $\phi$（欧拉函数）和 $\mu$（莫比乌斯函数）都是积性函数，可通过预处理快速计算。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e6 + 10;
int phi[N], mu[N];
bool vis[N];
vector<int> primes;

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

// 计算 sum(phi(i) * mu(i))
ll calc_sum(int n) {
    ll res = 0;
    for (int i = 1; i <= n; i++) {
        res += (ll)phi[i] * mu[i];
    }
    return res;
}

int main() {
    int n;
    cin >> n; // 输入 n
    sieve(n);
    ll ans = calc_sum(n);
    cout << "Sum: " << ans << "\n";
    return 0;
}

说明:

• 使用线性筛预处理 $\phi(i)$ 和 $\mu(i)$，时间复杂度 $O(n)$。
• $\phi(i)$ 表示 $i$ 的欧拉函数值，$\mu(i)$ 表示莫比乌斯函数值。
• 主函数计算 $\sum_{i=1}^n \phi(i) \cdot \mu(i)$，适用于多变量数论问题。