Farey Sequence：歐拉函數前綴和求解分數序列長度

題目大意

Farey 序列 F_n 定義為：所有分母 ≤ n、分子分母互質、真分數（分子 < 分母），按值升序排列。
例如：
F₂ = {1/2}
F₃ = {1/3, 1/2, 2/3}
F₄ = {1/4, 1/3, 1/2, 2/3, 3/4}
求 F_n 中元素個數。

數學關係

F_n 中分母為 k (2 ≤ k ≤ n) 的分數個數 = φ(k)（分子與 k 互質且 < k 的正整數個數）。
因此 |F_n| = Σ_{k=2..n} φ(k) = (Σ_{k=1..n} φ(k)) - 1

線性篩預處理 φ 前綴和

直接逐個計算 φ(k) 為 O(n√n) 會超時。採用**線性篩** O(n) 預處理所有 φ 值並構建前綴和。

關鍵代碼

const int MAXN = 1'000'005;
long long phi[MAXN], sum_phi[MAXN];

void linear_sieve_phi() {
    for (int i = 1; i < MAXN; ++i) phi[i] = i;
    // 偶數單獨處理
    for (int i = 2; i < MAXN; i += 2) phi[i] /= 2;
    // 線性篩核心
    for (int i = 3; i < MAXN; ++i) {
        if (phi[i] == i) { // i 是質數
            for (int j = i; j < MAXN; j += i)
                phi[j] = phi[j] / i * (i - 1);
        }
    }
    // 構建前綴和
    for (int i = 1; i < MAXN; ++i)
        sum_phi[i] = sum_phi[i-1] + phi[i];
}

int main() {
    linear_sieve_phi();
    long long n;
    while (cin >> n && n) {
        cout << sum_phi[n] - 1 << '\n'; // 減去 φ(1)=1 對應 0/1 不算真分數
    }
}

算法細節解析

1. 初始化：phi[i] = i
2. 質數篩選：phi[i] == i 判斷 i 為質數（未被篩過）
3. 質數倍數更新：對每個質數 p，其倍數 j 的 φ 值乘以 (p-1)/p（即 phi[j] = phi[j] / p * (p-1)）
4. 先除後乘：防止中間結果溢出，保證整數除法精確
5. 前綴和：O(1) 回答查詢

複雜度

• 預處理：O(MAXN) ≈ 10⁶ 操作，極快
• 查詢：O(1)
• 空間：O(MAXN)

總結

Farey 序列長度問題本質是**歐拉函數前綴和**。線性篩是預處理 φ 函數的標準利器，利用「質數倍數更新」特性實現 O(n) 複雜度，配合前綴和實現瞬間查詢，是數論競程必備模板。