HDU 2588 GCD：歐拉函數求解 gcd(i,n) > m 的計數

題目大意

給定 n, m，求滿足 1 ≤ i < n 且 gcd(i, n) > m 的整數 i 的個數。多測試用例。

數學轉化

1. gcd(i, n) 的值必然是 n 的**約數**
2. 設 d 為 n 的約數且 d > m，需計算 gcd(i, n) = d 的 i 個數
3. gcd(i, n) = d ⇔ gcd(i/d, n/d) = 1 且 d | i
4. 即 i = d × k，其中 1 ≤ k ≤ n/d 且 gcd(k, n/d) = 1
5. 這類 k 的個數正是 **歐拉函數 φ(n/d)**

因此答案 = Σ_{d|n, d>m} φ(n/d)

算法流程

1. 枚舉 n 的所有約數 d（只需枚舉到 √n）
2. 對每個約數 d：
   — 若 d > m，累加 φ(n/d)
   — 若 n/d > m 且 n/d ≠ d，累加 φ(d)
3. 單次查詢 O(√n × √n) = O(n) 粗略，實際 φ 計算 O(√(n/d))，總體極快

關鍵代碼

long long phi(long long x) {
    long long res = x, a = x;
    for (long long i = 2; i*i <= a; ++i) {
        if (a % i == 0) {
            res = res / i * (i - 1); // 先除後乘防溢出
            while (a % i == 0) a /= i;
        }
    }
    if (a > 1) res = res / a * (a - 1);
    return res;
}

int main() {
    int T; cin >> T;
    while (T--) {
        long long n, m; cin >> n >> m;
        long long ans = 0;
        for (long long d = 1; d*d <= n; ++d) {
            if (n % d) continue;
            if (d >= m && d*d != n) ans += phi(n/d);
            if (n/d >= m) ans += phi(d);
        }
        cout << ans << '\n';
    }
}

優化點

1. res = res / i * (i-1) 先除後乘，避免中間結果溢出 64 位
2. 約數枚舉到 √n，成對處理 d 和 n/d
3. 去重：d² = n 時只計算一次

複雜度

• 單次 φ 計算：O(√x)
• 約數個數 ≤ 2√n
• 單測試用例：O(√n × √n) = O(n) 理論上界，實際 n≤10⁹ 遠小於 1ms

總結

本題核心是將「gcd 條件」轉化為「約數枚舉 + 歐拉函數」。利用 gcd(i,n)=d ⇔ gcd(i/d, n/d)=1 這一基本數論性質，配合約數成對枚舉技巧，實現極簡高效的解法。