POJ 2478 Farey Sequence：用線性篩法求歐拉函數前綴和

問題描述

給定整數 n（n ≤ 1,000,000），要求計算 φ(2) + φ(3) + ... + φ(n)，其中 φ 為歐拉函數。輸入包含多組測試數據，以 0 結束。

核心思路：線性篩法預處理 φ 值

傳統試除法求單個 φ 函數複雜度為 O(√n)，多次查詢會超時。採用線性篩法（歐拉篩）可在 O(n) 時間內預處理出所有 φ(i)，再構建前綴和陣列 sum[i] = Σ φ(k)，每次查詢即為 O(1)。

線性篩法原理

• 維护一個質數列表 primes。
• 對每個 i，若 phi[i] == 0 則 i 為質數，phi[i] = i-1，加入質數表。
• 遍歷質數表中 p ≤ i 且 i*p ≤ n 的質數 p：
  • 若 i % p == 0：phi[i*p] = phi[i] * p；break（保證每個合數僅被其最小質因子篩一次）。
  • 否則：phi[i*p] = phi[i] * (p-1)。

關鍵代碼實現

const int MAXN = 1000000;
long long phi[MAXN + 1], sum[MAXN + 1];
vector primes;

void linear_sieve() {
    phi[1] = 1;
    for (int i = 2; i <= MAXN; ++i) {
        if (!phi[i]) {
            phi[i] = i - 1;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (i * p > MAXN) break;
            if (i % p == 0) {
                phi[i * p] = phi[i] * p;
                break;
            } else {
                phi[i * p] = phi[i] * (p - 1);
            }
        }
    }
    for (int i = 2; i <= MAXN; ++i) sum[i] = sum[i-1] + phi[i];
}

複雜度分析

• 預處理時間：O(MAXN) ≈ 10⁶ 操作，極快。
• 記憶體：phi、sum、primes 共約 20 MB。
• 單次查詢：O(1)。

常見誤區

• 篩法中 break 條件必須正確，否則會重複更新導致錯誤或退化為 O(n log log n)。
• phi[1] 定義為 1，但題目求和從 2 開始，故前綴和從 sum[2] 起算。
• 輸入以 0 結束，需處理多組測試案例。

總結

本題是線性篩法求歐拉函數的經典應用。掌握「每個合數僅被最小質因子篩一次」的核心邏輯，即可高效解決大範圍 φ 函數批量計算問題。