素数

在算法竞赛，数论是绕不开的话题，而素数（或称质数）则是数论中最基础也最重要的核心概念之一。无论是直接考察素数性质，还是作为其他数论算法（如欧拉函数、模运算、因数分解）的基础，对素数深刻的理解和高效的算法掌握都是冲击奖牌的关键。

1. 素数基础 (Prime Basics)

1.1 定义

一个大于 1 的正整数 $p$，如果除了 1 和它本身以外，不能被其他正整数整除，那么 $p$ 就被称为素数（质数）。大于 1 且不是素数的正整数称为合数。1 既不是素数也不是合数。

1.2 试除法判定素数 (Trial Division Primality Test)

这是最直观的素数判定方法。要判断一个整数 $n$ ($n > 1$) 是否为素数，我们只需检查是否存在一个整数 $d$ 使得 $2 \le d \le n-1$ 且 $n \pmod d = 0$。如果存在这样的 $d$，则 $n$ 是合数；否则，$n$ 是素数。

优化: 我们注意到，如果 $n$ 是一个合数，它必然有一个小于或等于 $\sqrt{n}$ 的因子。因为如果 $n = a \times b$ 且 $a, b > 1$，那么 $a$ 和 $b$ 中至少有一个不大于 $\sqrt{n}$。如果 $a > \sqrt{n}$ 且 $b > \sqrt{n}$，则 $a \times b > \sqrt{n} \times \sqrt{n} = n$，这与 $n = a \times b$ 矛盾。

因此，我们只需要检查 $2$ 到 $\lfloor \sqrt{n} \rfloor$ 之间的整数是否能整除 $n$ 即可。

代码实现:

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// 功能：判断 n 是否为素数 (试除法)
// 参数：n - 待判断的整数
// 返回值：true 如果 n 是素数，false 否则
bool is_p(ll n) {
    if (n < 2) return false; // 小于2的数不是素数
    // 只需检查到 sqrt(n)
    for (ll i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            return false; // 找到因子，不是素数
        }
    }
    return true; // 没有找到小于等于 sqrt(n) 的因子，是素数
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll n;
    cin >> n;
    if (is_p(n)) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }

    return 0;
}

复杂度分析:

• 时间复杂度: $O(\sqrt{n})$。对于单次判定，这个效率在 $n$ 较大时（例如 $10^{12}$ 或更大）是无法接受的。
• 空间复杂度: $O(1)$。

局限性: 当需要判断大量数字，或者数字本身非常大时，试除法效率低下。我们需要更快的工具。

2. 素数筛法 (Sieving for Primes)

当我们需要找出一定范围内的所有素数时（例如 $1$ 到 $N$），逐个使用试除法判断效率太低。总时间复杂度将达到 $O(N\sqrt{N})$。筛法应运而生，它们能以更低的时间复杂度预处理出范围内的所有素数。

2.1 埃拉托斯特尼筛法 (Sieve of Eratosthenes)

这是最古老、最经典的素数筛法。其基本思想是：从 2 开始，将每个素数的倍数都标记为合数。

步骤:

1. 创建一个布尔数组 isp[] （或 vis[]，表示 visited），大小为 $N+1$，初始化所有元素为 true（或 false，看标记方式），表示所有数初始时都“可能是素数”。isp[0] 和 isp[1] 标记为 false。
2. 从 $i = 2$ 开始遍历到 $N$：
   • 如果 isp[i] 为 true，说明 $i$ 是一个素数。
   • 将 $i$ 的所有倍数 $2i, 3i, 4i, \dots$ （不超过 $N$）标记为合数，即设置 isp[j] = false。
3. 遍历完成后，所有 isp[i] 仍为 true 的 $i$ 就是范围内的素数。

优化:

• 标记倍数时，可以从 $i \times i$ 开始。因为对于 $j < i$， $j \times i$ 这个合数一定在处理 $j$ 时被 $j$ 的某个素因子筛掉了。
• 外层循环只需要遍历到 $\sqrt{N}$ 即可标记所有合数，但为了得到所有素数列表，通常还是遍历到 $N$。

代码实现:

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e6 + 5; // 设定筛法上限
bool isp[N];         // isp[i] = false 表示 i 是素数, true 表示 i 是合数
vector<int> prm;     // 存储找到的素数

// 功能：埃氏筛法预处理 1 到 n 的素数
// 参数：n - 筛法上限
void sieve(int n) {
    fill(isp, isp + n + 1, false); // 初始化都为非合数（可能是素数）
    isp[0] = isp[1] = true;      // 0 和 1 不是素数

    for (int i = 2; i <= n; ++i) {
        if (!isp[i]) { // 如果 i 是素数
            prm.push_back(i); // 记录素数
            // 从 i*i 开始标记，且 j 需为 long long 防止溢出
            for (ll j = (ll)i * i; j <= n; j += i) {
                isp[j] = true; // 标记 i 的倍数为合数
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n; // 输入筛法上限

    sieve(n);

    // 输出找到的素数个数
    cout << "Primes found: " << prm.size() << "\n";
    // 可以选择性打印素数
    // for (int p : prm) {
    //     cout << p << " ";
    // }
    // cout << "\n";

    // 示例：判断 1 到 n 之间的数是否为素数
    // for(int i = 1; i <= n; ++i) {
    //     if (!isp[i]) {
    //         cout << i << " is prime.\n";
    //     } else {
    //         cout << i << " is composite.\n";
    //     }
    // }

    return 0;
}

复杂度分析:

• 时间复杂度: $O(N \log \log N)$。直观上看是 $\sum_{p \le N, p \text{ is prime}} \frac{N}{p} \approx N \sum_{p \le N} \frac{1}{p}$。根据素数定理的推论，素数的倒数和近似于 $\log \log N$。这是一个非常接近线性的复杂度，对于 $N$ 在 $10^7$ 甚至 $10^8$ 级别都非常高效。
• 空间复杂度: $O(N)$，主要用于存储 isp 数组。

2.2 线性筛 (Linear Sieve / Euler's Sieve)

埃氏筛法虽然高效，但仍有冗余：一个合数会被它的多个素因子重复标记。例如，12 会被 2 标记一次，也会被 3 标记一次。线性筛的目标是让每个合数只被其 最小的素因子 标记一次，从而达到严格的 $O(N)$ 时间复杂度。

核心思想:

维持一个当前找到的素数列表 prm。遍历 $i$ 从 2 到 $N$。

1. 如果 $i$ 没有被标记过，则 $i$ 是素数，将其加入 prm 列表。
2. 对于 prm 中的每个素数 $p_j$：
   • 标记 $i \times p_j$ 为合数。
   • 关键: 如果 $i \pmod{p_j} == 0$，则停止用 prm 中更大的素数去标记 $i$ 的倍数。
     • 原因: 如果 $i$ 是 $p_j$ 的倍数，即 $i = k \times p_j$，那么对于 prm 中下一个更大的素数 $p_{j+1}$，合数 $i \times p_{j+1} = k \times p_j \times p_{j+1}$。这个合数的最小素因子显然是 $p_j$（因为 $p_j < p_{j+1}$ 且 $p_j$ 是 $i$ 的因子，所以也是 $i \times p_{j+1}$ 的因子）。根据线性筛的原则（每个合数只被其最小素因子筛一次），$i \times p_{j+1}$ 应该在后面遍历到 $k \times p_{j+1}$ 时，被 $p_j$ 筛掉，而不是现在被 $p_{j+1}$ 筛掉。因此，一旦 $i$ 是 $p_j$ 的倍数，就必须 break，保证 $i \times p_j$ 是被其最小素因子 $p_j$ 筛掉的。

代码实现:

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e7 + 5; // 线性筛通常能处理更大的范围
bool isp[N];         // isp[i] = true 表示 i 不是素数 (是合数或 0, 1)
int prm[N / 10];     // 存储素数，大小可以估算或动态分配，这里给个大概
int cnt = 0;         // 素数计数器

// 功能：线性筛预处理 1 到 n 的素数
// 参数：n - 筛法上限
void sieve(int n) {
    fill(isp, isp + n + 1, false);
    isp[0] = isp[1] = true;
    cnt = 0;

    for (int i = 2; i <= n; ++i) {
        if (!isp[i]) { // i 是素数
            prm[cnt++] = i;
        }
        // 遍历已找到的素数 prm[j]
        for (int j = 0; j < cnt && (ll)i * prm[j] <= n; ++j) {
            isp[i * prm[j]] = true; // 标记 i * prm[j] 为合数
            // 关键：保证每个合数只被最小质因子筛掉
            if (i % prm[j] == 0) {
                break;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n; // 输入筛法上限

    sieve(n);

    cout << "Primes found: " << cnt << "\n";
    // 输出前 10 个素数
    // for (int i = 0; i < min(cnt, 10); ++i) {
    //     cout << prm[i] << " ";
    // }
    // cout << "\n";

    return 0;
}

复杂度分析:

• 时间复杂度: $O(N)$。每个合数 $x$ 只会被其最小素因子 $p$ 在 $i = x/p$ 时标记一次。外层循环 $N$ 次，内层 for 循环的 break 条件保证了每个合数只被访问一次。
• 空间复杂度: $O(N)$，用于存储 isp 数组和 prm 数组（素数个数约为 $N/\ln N$）。

应用场景:

线性筛是算法竞赛中预处理素数的最常用方法，尤其适用于需要 $N$ 以内所有素数，或者需要在 $O(N)$ 时间内预处理某些数论函数（如欧拉函数 $\phi(n)$、莫比ウス函数 $\mu(n)$）的场景。这些函数通常可以在线性筛的过程中一并计算出来。

3. 质因数分解 (Prime Factorization)

算术基本定理 (Fundamental Theorem of Arithmetic): 任何一个大于 1 的正整数 $N$ 都可以唯一地分解为有限个素数的乘积，形式为：

$$N = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k} = \prod_{i=1}^{k} p_i^{a_i} $$

其中 $p_1 < p_2 < \dots < p_k$ 是素数， $a_i \ge 1$ 是正整数。

质因数分解是数论问题的基石之一。

3.1 试除法分解 (Trial Division Factorization)

最朴素的方法是试除法。我们尝试用从 2 开始的整数去除 $N$。

步骤:

1. 遍历 $d$ 从 2 开始。
2. 如果 $d$ 能整除 $N$（即 $N \pmod d == 0$）：
   • $d$ 是 $N$ 的一个质因子。记录 $d$。
   • 将 $N$ 中所有的因子 $d$ 都除尽，即 $N = N / d$ 直到 $N$ 不能再被 $d$ 整除。同时记录 $d$ 的指数。
3. 继续增加 $d$，重复步骤 2。
4. 优化: 和素数判定类似，我们只需要尝试 $d$ 到 $\sqrt{N}$ 即可。当循环结束时，如果 $N > 1$，那么剩下的 $N$ 本身一定是一个大于 $\sqrt{N_{original}}$ 的素因子。
   • 证明: 假设循环结束后 $N>1$ 且 $N$ 是合数，那么 $N$ 必有一个小于等于 $\sqrt{N}$ 的素因子 $p$。由于我们是从小到大尝试除数的，这个素因子 $p$ 在之前的循环中一定会被尝试。如果 $p \le \sqrt{N_{original}}$，那么在循环到 $d=p$ 时，$N$ 就会被 $p$ 除尽，或者至少 $N$ 的值会变小。如果 $p > \sqrt{N_{original}}$，但仍然 $p \le \sqrt{N_{current}}$ (其中 $N_{current}$ 是循环到 $p$ 之前的 $N$ 值)，$p$ 也会被除掉。只有当 $N$ 在循环结束后剩下的值是一个大于 $\sqrt{N_{original}}$ 的素数时，才不会在 $d \le \sqrt{N_{original}}$ 的循环中被除掉。

代码实现:

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// 功能：对 n 进行质因数分解 (试除法)
// 参数：n - 待分解的正整数
// 返回值：一个 map，键是质因子，值是其指数
map<ll, int> factorize(ll n) {
    map<ll, int> factors;
    if (n < 2) return factors; // 处理边界情况

    // 尝试 2 到 sqrt(n) 的因子
    for (ll i = 2; i * i <= n; ++i) {
        if (n % i == 0) { // i 是一个因子
            int cnt = 0;
            while (n % i == 0) { // 除尽所有因子 i
                n /= i;
                cnt++;
            }
            factors[i] = cnt; // 记录质因子及其指数
        }
    }

    // 如果 n 在除完 <= sqrt(n) 的因子后仍然大于 1
    // 说明剩下的 n 是一个大于 sqrt(n_original) 的质因子
    if (n > 1) {
        factors[n] = 1;
    }

    return factors;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll n;
    cin >> n;

    map<ll, int> res = factorize(n);

    cout << n << " = ";
    bool first = true;
    for (auto const& [p, a] : res) {
        if (!first) {
            cout << " * ";
        }
        cout << p;
        if (a > 1) {
            cout << "^" << a;
        }
        first = false;
    }
    if (res.empty() && n >= 0) { // 处理 n=0, 1 的情况或 n 本身就是素数且小于等于1（虽然函数处理了<2）
        cout << n; // 保证输入 0 或 1 时有输出
    } else if (res.empty() && n < 0) {
         // 如果需要处理负数，可以先分解绝对值，再加负号
         cout << n;
    }
    cout << "\n";

    return 0;
}

复杂度分析:

• 时间复杂度: $O(\sqrt{N})$。对于单个数的分解，这个效率在 $N$ 达到 $10^{12}$ 左右是可接受的，但对于 $10^{18}$ 级别的 $N$ 则不够快。
• 空间复杂度: $O(\log N)$ 或 $O(\omega(N))$，其中 $\omega(N)$ 是 $N$ 的不同质因子个数。空间主要用于存储结果，因子个数通常不多。

优化: 如果需要对多个数进行质因数分解，且这些数范围不大（例如都在 $10^7$ 以内），可以先用筛法预处理出范围内的所有素数，然后只用这些素数去试除，可以略微加速。但主要瓶颈仍然是 $\sqrt{N}$。

3.2 Pollard's Rho 算法 (进阶)

对于非常大的数（例如 $N > 10^{15}$），$O(\sqrt{N})$ 的试除法分解变得不可行。这时需要更高级的算法，Pollard's Rho 是其中一种常用的 随机化 因子分解算法。

核心思想:

该算法试图利用随机函数在模 $N$ 的某个因子 $p$ 下产生的序列更快地出现循环（生日悖论的原理）来找到 $N$ 的一个非平凡因子（不是 1 或 $N$）。

它使用一个伪随机序列 $x_{i+1} = (x_i^2 + c) \pmod N$，并检查 $\gcd(|x_i - x_j|, N)$ 是否大于 1。通过 Floyd 判圈算法（快慢指针）来检测循环，即比较 $x_i$ 和 $x_{2i}$。如果 $\gcd(|x_i - x_{2i}|, N) = d > 1$，则 $d$ 可能是 $N$ 的一个因子。

• 如果 $d=N$，说明这次尝试失败（可能选取的 $c$ 或初始值 $x_0$ 不好，或者 $N$ 本身是素数），需要更换 $c$ 或 $x_0$ 重试。
• 如果 $1 < d < N$，则找到了一个因子 $d$。我们可以递归地对 $d$ 和 $N/d$ 进行分解。

注意: Pollard's Rho 是随机算法，不能保证一定能快速找到因子，但在实践中对于 $10^{18}$ 范围内的合数通常表现良好。它需要配合 Miller-Rabin 素数测试（见后文）一起使用：先用 Miller-Rabin 判断 $N$ 是否很可能是素数，如果是合数再用 Pollard's Rho 找因子。

复杂度: 启发式期望时间复杂度约为 $O(N^{1/4})$。

代码实现: 由于涉及较多的细节（大数乘法取模、GCD、随机化、递归），Pollard's Rho 的代码相对复杂。在 ICPC 竞赛中，如果不是专门准备数论难题的队伍，可能不会现场实现它，但了解其存在和适用场景是有益的。对于冲击金牌的选手，掌握 Pollard's Rho 是必要的。

（注：此处不提供 Pollard's Rho 的完整代码，因为它较为复杂且超出初学者/提高组的常规要求，其实现需要高效的模乘、模幂和 GCD 算法。）

4. 模运算与数论定理 (Modular Arithmetic & Theorems)

模运算是数论的基石，在算法竞赛中无处不在。素数在模运算中扮演着特殊的角色。

4.1 费马小定理 (Fermat's Little Theorem)

定理叙述: 如果 $p$ 是一个素数，并且整数 $a$ 不是 $p$ 的倍数（即 $a \pmod p \ne 0$，或 $\gcd(a, p) = 1$），那么：

$$a^{p-1} \equiv 1 \pmod p$$

推论: 对于任意整数 $a$（无论是否是 $p$ 的倍数），都有：

$$a^p \equiv a \pmod p$$

应用:

1. 快速计算模幂的逆元: 当模数 $p$ 是素数时，且 $a \not\equiv 0 \pmod p$，我们可以用费马小定理计算 $a$ 在模 $p$ 下的乘法逆元。因为 $a^{p-1} \equiv 1 \pmod p$，所以 $a \times a^{p-2} \equiv 1 \pmod p$。因此，$a^{p-2} \pmod p$ 就是 $a$ 的模 $p$ 逆元。这需要配合快速幂算法（见下文）来高效计算 $a^{p-2} \pmod p$。
2. 概率性素数测试 (Fermat Primality Test): 如果对于一个数 $n$，我们随机选取几个 $a$（满足 $1 < a < n$），计算 $a^{n-1} \pmod n$。如果结果不为 1，则 $n$ 必定是合数。如果对于所有选取的 $a$ 结果都为 1，则 $n$ 可能是素数。然而，存在一些合数（称为 Carmichael 数，例如 561）使得对于所有与其互质的 $a$，都有 $a^{n-1} \equiv 1 \pmod n$，因此费马测试是不可靠的，但它是更强的 Miller-Rabin 测试的基础。

快速幂 (Modular Exponentiation):

用于在 $O(\log b)$ 时间内计算 $a^b \pmod m$。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// 功能：计算 (a^b) % m
// 参数：a - 底数, b - 指数, m - 模数
ll power(ll a, ll b, ll m) {
    ll res = 1;
    a %= m; // 预处理，防止 a 过大
    while (b > 0) {
        if (b & 1) { // 如果 b 的当前最低位是 1
            res = (__int128)res * a % m; // 使用 __int128 防止中间结果溢出
        }
        a = (__int128)a * a % m; // a = a^2 % m
        b >>= 1; // b = b / 2
    }
    return res;
}

// 功能：使用费马小定理计算 a 在模素数 p 下的逆元
// 要求：p 是素数，a % p != 0
ll mod_inv_fermat(ll a, ll p) {
    if (a % p == 0) return -1; // 无逆元或非法输入
    return power(a, p - 2, p); // 计算 a^(p-2) mod p
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll a, p;
    // 示例：计算 3 在模 7 下的逆元
    a = 3; p = 7; // p=7 是素数
    ll inv = mod_inv_fermat(a, p);
    cout << "Inverse of " << a << " mod " << p << " is " << inv << endl; // 3*5 = 15 = 1 (mod 7) -> inv = 5
    cout << "Check: (" << a << " * " << inv << ") % " << p << " = " << (a * inv % p) << endl;

    // 示例：计算 2^10 mod 1000000007 (一个大素数)
    a = 2; ll b = 10; p = 1000000007;
    cout << "2^10 mod " << p << " = " << power(a, b, p) << endl;


    return 0;
}

注意: 在计算 res = res * a % m 和 a = a * a % m 时，如果 $a, res, m$ 都是 long long 级别（例如 $10^9$），它们的乘积可能会超过 long long 的范围（约 $9 \times 10^{18}$）。上述代码中使用了 __int128 来处理中间结果，这是 g++/clang 的一个扩展类型，可以存储更大的整数。如果编译器不支持 __int128，则需要使用更复杂的“龟速乘”（二进制乘法）或者基于 long double 的近似技巧来避免溢出。对于标准 ICPC 规则，通常允许使用 __int128。

快速幂复杂度: $O(\log b)$ 时间复杂度， $O(1)$ 空间复杂度（递归实现则为 $O(\log b)$ 栈空间）。

4.2 欧拉定理 (Euler's Theorem)

费马小定理是欧拉定理在模数为素数时的特例。欧拉定理适用于模数为任意正整数的情况。

欧拉函数 (Euler's Totient Function) $\phi(n)$: $\phi(n)$ 定义为小于或等于 $n$ 的正整数中与 $n$ 互质（最大公约数为 1）的数的个数。

计算 $\phi(n)$: 如果 $n$ 的标准质因数分解为 $n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$，则 $\phi(n)$ 的计算公式为：

$$\phi(n) = n \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \dots \left(1 - \frac{1}{p_k}\right) = n \prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right) $$

展开后也可以写成：

$$\phi(n) = p_1^{a_1-1}(p_1-1) p_2^{a_2-1}(p_2-1) \dots p_k^{a_k-1}(p_k-1) $$

性质:

• 如果 $p$ 是素数，$\phi(p) = p-1$。
• 如果 $p$ 是素数，$k \ge 1$，则 $\phi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)$。
• 欧拉函数是 积性函数：如果 $\gcd(m, n) = 1$，则 $\phi(mn) = \phi(m)\phi(n)$。

欧拉定理叙述: 如果整数 $a$ 和正整数 $n$ 互质（即 $\gcd(a, n) = 1$），那么：

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

扩展欧拉定理 (或称欧拉降幂公式): 对于任意整数 $a$ 和正整数 $n \ge 1$，以及任意整数 $b \ge \phi(n)$，有：

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

注意: 这个扩展定理 不要求 $a$ 与 $n$ 互质。当 $\gcd(a,n) \ne 1$ 时，指数不能简单地对 $\phi(n)$ 取模，需要加上 $\phi(n)$ 来保证正确性（仅当 $b < \phi(n)$ 时才需要判断，若 $b \ge \phi(n)$ 则直接套用公式）。

应用:

1. 计算模幂逆元 (通用情况): 如果 $\gcd(a, n) = 1$，则 $a$ 模 $n$ 的逆元是 $a^{\phi(n)-1} \pmod n$。这需要先计算 $\phi(n)$。
2. 指数降幂: 在计算 $a^b \pmod n$ 时，如果指数 $b$ 非常大，可以使用欧拉定理（或扩展欧拉定理）将指数 $b$ 对 $\phi(n)$（或在某些情况下是 $\phi(n)$ 再加 $\phi(n)$）取模，从而减小指数的规模。这对于处理形如 $a^{b^c} \pmod n$ 的问题非常有用。

计算 $\phi(n)$ 的方法:

• 单个计算: 利用质因数分解公式。先对 $n$ 进行质因数分解 $n = p_1^{a_1} \dots p_k^{a_k}$，然后套用公式 $\phi(n) = n \prod (1 - 1/p_i)$。时间复杂度主要取决于质因数分解，即 $O(\sqrt{n})$。

  #include <bits/stdc++.h>
  
  using namespace std;
  using ll = long long;
  
  // 功能：计算 phi(n) (基于质因数分解)
  // 参数：n - 正整数
  // 返回值：phi(n)
  ll phi(ll n) {
      if (n == 0) return 0; // phi(0) 无定义或视情况处理
      ll res = n;
      for (ll i = 2; i * i <= n; ++i) {
          if (n % i == 0) {
              res = res / i * (i - 1); // 等价于 res *= (1 - 1/i)
              while (n % i == 0) {
                  n /= i;
              }
          }
      }
      if (n > 1) { // 如果最后剩下一个大于 sqrt(n_original) 的质因子
          res = res / n * (n - 1);
      }
      return res;
  }
  
  int main() {
      ios::sync_with_stdio(0);
      cin.tie(0);
      cout.tie(0);
  
      ll n;
      cin >> n;
      cout << "phi(" << n << ") = " << phi(n) << endl;
      return 0;
  }
  

  复杂度: $O(\sqrt{n})$。

• 批量计算 (线性筛): 可以在线性筛的同时计算出 $1$ 到 $N$ 所有数的欧拉函数值。

  #include <bits/stdc++.h>
  
  using namespace std;
  using ll = long long;
  
  const int N = 1e7 + 5;
  bool isp[N];
  int prm[N / 10];
  int cnt = 0;
  int phi_val[N]; // 存储 phi 值
  
  // 功能：线性筛计算 1 到 n 的 phi 值
  // 参数：n - 上限
  void sieve_phi(int n) {
      fill(isp, isp + n + 1, false);
      isp[0] = isp[1] = true;
      phi_val[1] = 1; // phi(1) = 1
      cnt = 0;
  
      for (int i = 2; i <= n; ++i) {
          if (!isp[i]) { // i 是素数
              prm[cnt++] = i;
              phi_val[i] = i - 1; // phi(p) = p - 1
          }
          for (int j = 0; j < cnt && (ll)i * prm[j] <= n; ++j) {
              int pj = prm[j];
              isp[i * pj] = true;
              if (i % pj == 0) { // pj 是 i 的最小质因子
                  // phi(i * pj) = phi(i) * pj
                  // 因为 i 包含了 pj, i*pj 与 i 相比，只是 pj 的指数增加了 1
                  // 根据 phi(p^k) = p^(k-1)(p-1) 推导
                  phi_val[i * pj] = phi_val[i] * pj;
                  break;
              } else { // pj 不是 i 的最小质因子 (即 gcd(i, pj) = 1)
                  // phi 是积性函数: phi(i * pj) = phi(i) * phi(pj)
                  phi_val[i * pj] = phi_val[i] * (pj - 1); // phi(pj) = pj - 1
              }
          }
      }
  }
  
  int main() {
      ios::sync_with_stdio(0);
      cin.tie(0);
      cout.tie(0);
  
      int n;
      cin >> n;
  
      sieve_phi(n);
  
      // 打印前 10 个 phi 值
      for (int i = 1; i <= min(n, 10); ++i) {
          cout << "phi(" << i << ") = " << phi_val[i] << "\n";
      }
  
      return 0;
  }
  

  复杂度: $O(N)$ 时间复杂度， $O(N)$ 空间复杂度。

4.3 模逆元 (Modular Inverse)

给定整数 $a$ 和 $n$，如果存在一个整数 $x$ 使得 $ax \equiv 1 \pmod n$，则称 $x$ 是 $a$ 模 $n$ 的乘法逆元。记作 $a^{-1} \pmod n$。

存在条件: $a$ 模 $n$ 的逆元存在的充要条件是 $\gcd(a, n) = 1$。

求解方法:

1. 费马小定理: 当 $n$ 是素数且 $a \not\equiv 0 \pmod n$ 时，逆元为 $a^{n-2} \pmod n$。需要 $O(\log n)$ 的快速幂。

2. 欧拉定理: 当 $\gcd(a, n) = 1$ 时，逆元为 $a^{\phi(n)-1} \pmod n$。需要计算 $\phi(n)$（若单次计算是 $O(\sqrt{n})$ 或 预处理 $O(N)$）和快速幂 $O(\log n)$。

3. 扩展欧几里得算法 (Extended Euclidean Algorithm, ExGCD): 这是求解模逆元最通用和常用的方法，因为它不要求 $n$ 是素数，只需要 $\gcd(a, n) = 1$。 扩展欧几里得算法用于求解方程 $ax + ny = \gcd(a, n)$ 的一组整数解 $(x, y)$。 如果 $\gcd(a, n) = 1$，那么方程变为 $ax + ny = 1$。对这个方程两边同时取模 $n$，得到 $ax \equiv 1 \pmod n$。因此，ExGCD 算出的 $x$ (可能需要调整到 $[0, n-1]$ 范围内) 就是 $a$ 模 $n$ 的逆元。

   代码实现 (ExGCD):

   #include <bits/stdc++.h>
   
   using namespace std;
   using ll = long long;
   
   // 功能：扩展欧几里得算法，求解 ax + by = gcd(a, b)
   // 参数：a, b - 输入整数
   //       x, y - 引用参数，返回方程的一组特解
   // 返回值：gcd(a, b)
   ll exgcd(ll a, ll b, ll &x, ll &y) {
       if (b == 0) {
           x = 1;
           y = 0;
           return a;
       }
       ll d = exgcd(b, a % b, y, x); // 注意 x, y 的位置交换
       y -= (a / b) * x;
       return d;
   }
   
   // 功能：计算 a 模 n 的逆元 (使用 ExGCD)
   // 要求：gcd(a, n) = 1
   // 返回值：a 的模 n 逆元，若不存在则返回 -1 (或其他错误标记)
   ll mod_inv_exgcd(ll a, ll n) {
       ll x, y;
       ll d = exgcd(a, n, x, y);
       if (d != 1) {
           return -1; // 逆元不存在
       }
       // x 可能是负数，调整到 [0, n-1] 范围
       return (x % n + n) % n;
   }
   
   int main() {
       ios::sync_with_stdio(0);
       cin.tie(0);
       cout.tie(0);
   
       ll a, n;
       // 示例：计算 3 模 7 的逆元
       a = 3; n = 7;
       ll inv = mod_inv_exgcd(a, n);
       if (inv != -1) {
           cout << "Inverse of " << a << " mod " << n << " is " << inv << endl; // 5
       } else {
           cout << "Inverse does not exist." << endl;
       }
   
       // 示例：计算 6 模 9 的逆元
       a = 6; n = 9; // gcd(6, 9) = 3 != 1
       inv = mod_inv_exgcd(a, n);
       if (inv != -1) {
           cout << "Inverse of " << a << " mod " << n << " is " << inv << endl;
       } else {
           cout << "Inverse does not exist." << endl; // 不存在
       }
   
       return 0;
   }
   

   复杂度: 扩展欧几里得算法的时间复杂度与欧几里得算法相同，为 $O(\log(\min(a, b)))$ 或 $O(\log n)$。

选择哪种方法?

• 如果模数 $p$ 是素数，费马小定理最简单直接。
• 如果模数 $n$ 不是素数，或者需要处理 $n$ 是素数和合数混合的情况，扩展欧几里得算法是标准做法。
• 欧拉定理法需要计算 $\phi(n)$，通常不如 ExGCD 直接。但在某些需要预计算 $\phi$ 值的场景下也可行。

5. 大素数判定 (Large Primality Testing)

当需要判断的数 $n$ 非常大（例如 $10^{18}$ 甚至更大），试除法 $O(\sqrt{n})$ 和筛法 $O(N)$ 都不适用。这时需要概率性素数测试算法。

5.1 Miller-Rabin 算法

Miller-Rabin 是目前在算法竞赛中最常用的大数素性测试算法。它是一种 随机化算法，能够在 $O(k \log^3 n)$ 的时间内以非常高的概率判断一个数 $n$ 是否为素数（$k$ 是测试的轮数）。

核心思想:

基于费马小定理和二次探测定理。

1. 二次探测定理: 如果 $p$ 是一个素数，且 $x$ 是一个整数使得 $0 < x < p$，则方程 $x^2 \equiv 1 \pmod p$ 的解只有 $x=1$ 或 $x=p-1$。
   • 推论: 如果找到一个 $x$ 使得 $x^2 \equiv 1 \pmod p$ 但 $x \not\equiv 1 \pmod p$ 且 $x \not\equiv p-1 \pmod p$，则 $p$ 一定是合数。

算法步骤:

1. 处理小情况: 如果 $n < 2$，则 $n$ 不是素数。如果 $n=2$ 或 $n=3$，则 $n$ 是素数。如果 $n$ 是偶数且 $n > 2$，则 $n$ 是合数。
2. 分解 $n-1$: 将 $n-1$ 表示为 $n-1 = 2^s \times d$，其中 $d$ 是奇数，$s \ge 0$。
3. 进行 $k$ 轮测试:
   • 随机选择一个整数 $a$，满足 $1 < a < n-1$。（实践中通常选择一些小的素数作为基底 $a$，例如 {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}。对于 $n < 2^{64}$ 的范围，使用特定的几组基底就能做到 100% 确定性判断）。
   • 计算 $x = a^d \pmod n$。
   • 如果 $x = 1$ 或 $x = n-1$，则 $n$ 可能是素数，继续下一轮测试（或换一个基底 $a$）。
   • 否则，进行 $s-1$ 次平方探测：
     • 重复 $s-1$ 次：令 $x = x^2 \pmod n$。
     • 如果在某次平方后 $x = n-1$，则 $n$ 可能是素数，跳出内层循环，继续下一轮测试。
     • 如果在某次平方后 $x = 1$（但之前的 $x$ 不是 $n-1$），根据二次探测定理，$n$ 是合数，直接返回 false。
   • 如果 $s$ 次循环（包括初始的 $a^d$）结束后， $x$ 仍然不等于 $n-1$，则说明费马小定理 $a^{n-1} \equiv a^{2^s d} \equiv 1 \pmod n$ 不成立（或者在中间步骤违反了二次探测），因此 $n$ 是合数，返回 false。
4. 通过所有测试: 如果 $n$ 通过了 $k$ 轮测试（对于所有选定的基底 $a$），则我们 高度确信 $n$ 是素数，返回 true。

确定性基底: 对于 $n < 2^{64}$，使用以下基底 {2, 325, 9375, 28178, 450775, 9780504, 1795265022} 进行测试，可以得到确定性的结果（如果通过则一定是素数）。在 ICPC 中常用这组基底。

代码实现 (Miller-Rabin):

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// 使用 __int128 防止模乘溢出
using i128 = __int128;

// 快速幂 (底数和模数可能很大)
ll power(ll a, ll b, ll m) {
    ll res = 1;
    a %= m;
    while (b > 0) {
        if (b & 1) res = (i128)res * a % m;
        a = (i128)a * a % m;
        b >>= 1;
    }
    return res;
}

// Miller-Rabin 单轮测试
// n: 待测数, a: 基底
bool miller_rabin_check(ll n, ll a) {
    if (a % n == 0) return true; // a=0 或 a 是 n 的倍数，无法判断，视为通过

    ll d = n - 1;
    while (d % 2 == 0) d /= 2; // n-1 = 2^s * d

    ll x = power(a, d, n); // 计算 a^d mod n

    if (x == 1 || x == n - 1) return true; // 可能为素数

    while (d != n - 1) {
        x = (i128)x * x % n; // x = x^2 mod n
        d *= 2;             // 对应指数 d*2

        if (x == 1) return false; // 二次探测失败，一定是合数 (因为之前的 x != n-1)
        if (x == n - 1) return true; // 通过二次探测，可能为素数
    }

    // 循环结束 x 仍不为 n-1，说明 a^(n-1) != 1 mod n
    return false; // 合数
}

// Miller-Rabin 素性测试主函数
// n: 待测数
// k: 测试轮数 (或使用确定性基底时忽略)
bool is_prime_mr(ll n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0) return false; // 偶数

    // 使用确定性基底 (对于 n < 2^64)
    // ll bases[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}; // 适用于较小范围
    ll bases[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; // 适用于 n < 2^64

    for (ll a : bases) {
        if (n == a) return true; // n 本身就是基底之一
        if (!miller_rabin_check(n, a)) {
            return false; // 只要有一轮失败，就是合数
        }
    }

    return true; // 通过所有确定性基底测试，是素数
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll n;
    // 测试一些数
    ll tests[] = {2, 3, 4, 17, 561, 1000000007, 999999999989LL, 1000000000000000003LL};

    for (ll t : tests) {
        if (is_prime_mr(t)) {
            cout << t << " is prime.\n";
        } else {
            cout << t << " is composite.\n";
        }
    }
    // 561 is composite. (Carmichael number)
    // 999999999989 is prime.
    // 1000000000000000003 is prime.

    return 0;
}

复杂度分析:

• 时间复杂度: 一次 miller_rabin_check 的复杂度主要是快速幂和平方探测，约为 $O(\log^3 n)$（如果认为模乘是 $O(\log^2 n)$）或 $O(\log n \times \log n) = O(\log^2 n)$（如果认为模乘是 $O(1)$ 或 $O(\log n)$，这取决于实现，通常视为 $O(\log n)$ 或更快）。进行 $k$ 轮测试，总复杂度为 $O(k \log^3 n)$ 或 $O(k \log^2 n)$。使用确定性基底时 $k$ 是常数。
• 空间复杂度: $O(1)$ (不计 __int128 的开销)。

适用场景: 判断 $10^9$ 到 $10^{18}$ 甚至更大范围内的单个整数是否为素数。是 Pollard's Rho 分解算法的前置步骤。

6. 实战

1. 整数溢出: 在处理大数时，尤其是乘法和快速幂中，中间结果很容易超过 long long 的范围。务必使用 __int128 (如果可用) 或实现防溢出模乘（龟速乘）。
2. 选择合适的算法:
   • 判断单个小整数（如 $N \le 10^7$）是否为素数：可以直接用预处理的筛法 isp[] 数组 $O(1)$ 查询。
   • 判断单个中等整数（如 $N \le 10^{14}$）是否为素数：试除法 $O(\sqrt{N})$ 可能可行。
   • 判断单个大整数（如 $N \le 10^{18}$ 或更大）：必须用 Miller-Rabin $O(k \log^2 N)$。
   • 找出 $1$ 到 $N$ ( $N \le 10^7$ 或 $10^8$) 的所有素数：线性筛 $O(N)$ 是最佳选择。埃氏筛 $O(N \log \log N)$ 也可以。
   • 质因数分解小整数（$N \le 10^7$）：可以结合筛法预处理素数，再用这些素数试除，复杂度仍是 $O(\sqrt{N})$ 或更快（如果因子都很小）。
   • 质因数分解中等整数（$N \le 10^{14}$）：试除法 $O(\sqrt{N})$。
   • 质因数分解大整数（$N \ge 10^{15}$）：先用 Miller-Rabin 判素，如果是合数，用 Pollard's Rho $O(N^{1/4})$ 尝试分解。
3. 边界条件: 注意处理 $0, 1, 2$ 等特殊情况。负数通常不讨论素性，但如果题目涉及，需明确定义或按题意处理。
4. 复杂度意识: 时刻关注算法的时间和空间复杂度是否满足题目限制。尤其是在循环嵌套或递归中。
5. 模板化: 将筛法、快速幂、ExGCD、Miller-Rabin 等常用数论算法写成可靠的模板，比赛时可以快速调用。
6. 组合使用: 很多数论题需要结合多种技术，例如先筛素数，再用素数进行分解或计算欧拉函数，最后结合模运算定理求解。

7. 总结

素数是数论世界的基础构件，掌握素数相关的核心概念和高效算法是必备技能。

• 基础: 理解素数定义，掌握 $O(\sqrt{N})$ 的试除法判定和分解。
• 核心: 精通埃氏筛 $O(N \log \log N)$ 和线性筛 $O(N)$，能在 $O(N)$ 内预处理素数及相关积性函数（如 $\phi$）。
• 进阶: 熟练运用费马小定理、欧拉定理进行模逆元计算和指数降幂，掌握 $O(\log n)$ 的快速幂和扩展欧几里得算法。
• 高阶: 掌握 $O(k \log^2 N)$ 的 Miller-Rabin 大数素性测试，了解 $O(N^{1/4})$ 的 Pollard's Rho 大数分解算法。
• 实战: 注意数据范围、整数溢出、边界条件，根据问题规模选择最合适的算法，并能够灵活组合运用这些工具。