POJ 2478 Farey Sequence：歐拉函數前綴和求真分數個數

問題描述

Farey 序列 F_n 定義為：所有分母 ≤ n、分子分母互質的真分數 a/b (0 < a < b ≤ n)，按值升序排列。求 F_n 中項數 N(n)。

例如：F_5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5}，共 9 項。

數學轉化

N(n) = Σ_{b=2}^n φ(b)，其中 φ(b) 是歐拉函數（1~b 中與 b 互質的數的個數）。

證明：對每個分母 b，合法分子數恰為 φ(b)。

線性篩法預計算 φ(1..10^6)

#include <cstdio>

const int MAXN = 1000000;
int phi[MAXN + 1];
long long sumPhi[MAXN + 1];  // 前綴和

void linearSievePhi() {
    static int primes[MAXN];
    static bool isComp[MAXN + 1];
    int cnt = 0;
    phi[1] = 1;
    for (int i = 2; i <= MAXN; ++i) {
        if (!isComp[i]) {
            primes[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < cnt && i * primes[j] <= MAXN; ++j) {
            int p = primes[j];
            int ip = i * p;
            isComp[ip] = true;
            if (i % p == 0) {
                phi[ip] = phi[i] * p;
                break;
            } else {
                phi[ip] = phi[i] * (p - 1);
            }
        }
    }
    // 前綴和
    for (int i = 1; i <= MAXN; ++i)
        sumPhi[i] = sumPhi[i - 1] + phi[i];
}

int main() {
    linearSievePhi();
    int n;
    while (scanf("%d", &n) == 1 && n) {
        printf("%lld\n", sumPhi[n]);
    }
    return 0;
}

關鍵點解析

1. 線性篩 O(N)：每個合數只被最小質因子篩一次，比 Eratosthenes 篩更快
2. φ 函數遞推公式：
   • i % p == 0: φ(i*p) = φ(i) * p
   • i % p != 0: φ(i*p) = φ(i) * (p-1)
3. 前綴和預計算：查詢 O(1)，多測試用例極快
4. 長整型輸出：N(10^6) ≈ 3e11，需 long long / %lld

數值規模參考

相關題目延伸

• HDU 2588 / 2013 / 3501：GCD 相關計數
• SPOJ ETF：單次查詢 φ(n)
• Codeforces 622F：Σ k^p 模運算