题解 | #【模板】欧拉函数Ⅰ ‖ 单个整数#

题目链接

【模板】欧拉函数Ⅰ ‖ 单个整数

题目描述

给定多次询问，每次输入一个正整数 $n$ ，输出欧拉函数 $\varphi(n)$ ，即区间 $[1, n]$ 内与 $n$ 互质的整数个数。

解题思路

欧拉函数公式：若 $n$ 的不同质因子集合为 $\{p\}$ ，则
$\varphi(n) = n \cdot \prod_{p\mid n} \left(1 - \frac{1}{p}\right).$
做法（试除分解质因子）：
- 设答案 $\text{ans} = n$ 。从 $i=2$ 开始试除，直到 $i\cdot i \le n$ 。
- 一旦发现质因子 $p\mid n$ ，就把 $n$ 中的 $p$ 全部除尽，并令 $\text{ans} = \text{ans} / p \cdot (p-1)$ 。
- 试除结束后，若剩余的 $n>1$ ，说明 $n$ 本身是一个质因子，同样令 $\text{ans} = \text{ans} / n \cdot (n-1)$ 。
边界： $n=1$ 时 $\varphi(1)=1$ 。 $n$ 为质数时 $\varphi(n)=n-1$ 。
复杂度：单次询问试除到 $\sqrt{n}$ ，时间复杂度 $\mathcal{O}(\sqrt{n})$ ，空间复杂度 $\mathcal{O}(1)$ 。多次询问可逐个独立处理。

代码

c++
java
python

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

// 计算单个整数的欧拉函数 φ(n)
static inline int64 phi(int64 n) {
    if (n == 1) return 1;               // 边界：φ(1) = 1
    int64 ans = n;
    for (int64 p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            // 将质因子 p 的幂全部除尽
            while (n % p == 0) n /= p;
            // 按公式 ans = ans / p * (p - 1)
            ans = ans / p * (p - 1);
        }
    }
    // 若此时 n > 1，说明剩余的是一个大于 sqrt(原始 n) 的质因子
    if (n > 1) ans = ans / n * (n - 1);
    return ans;
}

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

    int q; // 询问次数
    if (!(cin >> q)) return 0;
    while (q--) {
        long long n;
        cin >> n;
        cout << phi(n) << '\n';
    }
    return 0;
}

import java.util.*;

public class Main {
    // 计算单个整数的欧拉函数 φ(n)
    static long phi(long n) {
        if (n == 1) return 1; // 边界处理
        long ans = n;
        for (long p = 2; p * p <= n; ++p) {
            if (n % p == 0) {
                while (n % p == 0) n /= p; // 去掉质因子 p 的所有幂
                ans = ans / p * (p - 1);   // 按公式更新答案
            }
        }
        if (n > 1) ans = ans / n * (n - 1); // 处理剩余的大质因子
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int q = sc.nextInt();
        while (q-- > 0) {
            long n = sc.nextLong();
            System.out.println(phi(n));
        }
    }
}

# 计算单个整数的欧拉函数 φ(n)
def phi(n: int) -> int:
    if n == 1:
        return 1  # 边界：φ(1) = 1
    ans = n
    p = 2
    # 试除到 sqrt(n)
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p  # 去掉质因子 p 的所有幂
            ans = ans // p * (p - 1)  # 按公式更新答案
        p += 1
    # 若剩余 n > 1，则其为一个大质因子
    if n > 1:
        ans = ans // n * (n - 1)
    return ans


q = int(input())
for _ in range(q):
    n = int(input())
    print(phi(n))

算法及复杂度

算法：分解 $n$ 的不同质因子，按 $\varphi(n) = n \cdot \prod_{p\mid n} (1 - 1/p)$ 更新答案。
时间复杂度：单次 $\mathcal{O}(\sqrt{n})$ 。
空间复杂度： $\mathcal{O}(1)$ 。