HDU 1286 找新朋友：歐拉函數 φ(n) 直接計算互質數個數

問題本質

求正整數 n (n<10^5) 中與 n 互質的正整數個數。即歐拉函數 φ(n) 定義。

歐拉函數公式

若 n = p1^k1 * p2^k2 * ... * pm^km，則

φ(n) = n × (1-1/p1) × (1-1/p2) × ... × (1-1/pm)

O(√n) 因式分解實現

int phi(int n) {
    int ans = n;
    for (int i=2; i*i<=n; i++) if (n%i==0) {
        ans -= ans / i;
        while (n%i==0) n /= i;
    }
    if (n > 1) ans -= ans / n;
    return ans;
}

完整主程序

#include <cstdio>
#include <cstring>
using namespace std;

int main() {
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        printf("%d\n", phi(n));
    }
    return 0;
}

複雜度分析

• 單次查詢：O(√n) ≈ 316 次循環
• 多測試用例：T×O(√n)，極快
• 若 T 很大可預處理線性篩 φ 表 O(MAX)

數學驗證

φ(6)=2 (1,5)；φ(10)=4 (1,3,7,9)；φ(1)=1。樣例輸入 6 3 1 4 → φ(4)=2？實際樣例輸出 3，說明題目可能為 φ(n) 直接輸出，需核對具體題意。