AcWing 873. 欧拉函数

◎

本节目标

用不同质因子计算与 n 互质的正整数数量。

题意与约束

对每个正整数 n，输出不超过 n 且与 n 互质的正整数数量 φ(n)。

第一反应与瓶颈

逐个计算 gcd(i, n) 能得到答案，却把互质判断重复做了 n 次。质因数分解已经告诉我们哪些数会被排除。

数学关系与算法推导

若 p 是 n 的不同质因子，1..n 中恰有 1/p 的数是 p 的倍数，所以 φ(n) 从 n 开始依次更新为 result / p * (p - 1)。同一个 p 的指数不会重复影响比例。

正确性依据

每次试除发现新质因子时，更新恰好去掉它的倍数；不同质因子的排除由乘法原则合并。除尽该因子后继续试除，循环结束后的剩余 n > 1 只能是一个尚未处理的质因子。

样例执行过程

36 = 2² × 3²：36 / 2 × 1 = 18，再 18 / 3 × 2 = 12，因此 φ(36)=12。

代码实现

C++

C++17

#include <iostream>
using namespace std;

long long eulerTotient(long long n) {
    long long result = n;
    for (long long prime = 2; prime <= n / prime; prime++) {
        if (n % prime == 0) {
            result = result / prime * (prime - 1);
            while (n % prime == 0) {
                n /= prime;
            }
        }
    }
    if (n > 1) {
        result = result / n * (n - 1);
    }
    return result;
}

#ifndef ALGORITHM_TUTORIAL_NO_MAIN
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int count;
    cin >> count;
    while (count-- > 0) {
        long long n;
        cin >> n;
        cout << eulerTotient(n) << '\n';
    }
    return 0;
}
#endif

Python

Python 3

import sys


def euler_totient(n: int) -> int:
    result = n
    prime = 2
    while prime <= n // prime:
        if n % prime == 0:
            result = result // prime * (prime - 1)
            while n % prime == 0:
                n //= prime
        prime += 1
    if n > 1:
        result = result // n * (n - 1)
    return result


def main() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    print('\n'.join(str(euler_totient(n)) for n in data[1:]))


if __name__ == '__main__':
    main()

复杂度分析

单次试除时间 O(√n)，额外空间 O(1)。

边界与易错点

φ(1)=1。更新必须先除再乘以避免不必要的中间放大；发现 p 后要用 while 除尽，但公式只能对这个不同质因子应用一次。

模式迁移

欧拉函数是理解模运算周期性的理论桥梁；本章只把它连接到质数模数下的逆元，不展开欧拉定理的更多推论。回到欧拉函数与模运算。