POJ 2407 / UVA 10299 Relatives：歐拉函數經典應用詳解

題目大意

給定一個正整數 n（n ≤ 1,000,000,000），求小於或等於 n 且與 n 互質的正整數個數。這正是著名的歐拉函數 φ(n)。特別注意：當 n = 1 時，答案應為 0（UVA 強制要求，POJ 對 1 也接受）。

核心思路

直接套用歐拉函數公式：φ(n) = n × ∏(1 - 1/p)，其中 p 為 n 的所有不同質因數。演算法步驟如下：

1. 初始化 res = n。
2. 從 2 遍歷到 √n，若 i 能整除 n，則 i 是質因數，更新 res = res - res / i，並將 n 除盡所有 i。
3. 迴圈結束後，若 n > 1，說明剩下一個大於 √n 的質因數，再做一次 res = res - res / n。
4. 特判 n == 1 輸出 0。

參考代碼 (C++)

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long LL;

int euler(int n) {
    int res = n;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            n /= i;
            res = res - res / i;
            while (n % i == 0) n /= i;
        }
    }
    if (n != 1) res = res - res / n;
    return res;
}

int main() {
    int n;
    while (cin >> n && n != 0) {
        if (n == 1) puts("0");
        else printf("%d\n", euler(n));
    }
    return 0;
}

複雜度分析

時間複雜度 O(√n)，空間複雜度 O(1)，完全滿足 n ≤ 1e9 的限制。