HDU 2841 Visible Trees：網格可見樹木的數論計數

HDU 2841 Visible Trees：網格可見樹木的數論計數

m×n 網格（座標從 (1,1) 開始），觀察者在 (0,0) 向右上看。若兩棵樹與原點共線且距離較近者擋住較遠者，求可見樹木數。等價於：計算有多少個格點 (x,y) 滿足 1≤x≤m, 1≤y≤n 且 gcd(x,y)=1。

數學建模

樹木在 (x,y) 可見 ⇔ 線段 (0,0)-(x,y) 上無其他整點 ⇔ gcd(x,y) = 1。

答案 = ∑ₓ₌₁ᵐ ∑ᵧ₌₁ⁿ [gcd(x,y)=1]

歐拉篩法預計算 φ 函數

利用結構：固定 x，滿足 gcd(x,y)=1 的 y 個數為 φ(x) 在範圍內的分布。但更直接：

ans = ∑ₓ₌₁ᵐ (對於這個 x，有多少 y≤n 與 x 互質)

包含-排斥原理快速計算

對於固定 x，設其質因子為 p₁, p₂, ..., pₖ。與 x 不互質的 y 個數 = 包含至少一個 pᵢ 的倍數個數。用容斥原理：

不互質數 = ∑|Aᵢ| - ∑|Aᵢ∩Aⱼ| + ∑|Aᵢ∩Aⱼ∩Aₖ| - ...
互質數 = n - 不互質數

完整算法流程

1. 線性篩法預計算所有數的質因子分解（去重）
2. 對每個 x = 2..m，用其質因子對 n 執行容斥，得互質 y 數
3. x=1 時所有 y 都互質，貢獻 n
4. 累加得到答案

C++ 參考實現

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000;
vector<int> prime_factors[MAXN + 5];
int primes[MAXN + 5], pcnt;
bool is_composite[MAXN + 5];

void linear_sieve() {
    for (int i = 2; i <= MAXN; ++i) {
        if (!is_composite[i]) {
            primes[pcnt++] = i;
            prime_factors[i].push_back(i);
        }
        for (int j = 0; j < pcnt && i * primes[j] <= MAXN; ++j) {
            int x = i * primes[j];
            is_composite[x] = true;
            prime_factors[x] = prime_factors[i];
            if (prime_factors[x].empty() || prime_factors[x].back() != primes[j])
                prime_factors[x].push_back(primes[j]);
            if (i % primes[j] == 0) break;
        }
    }
}

long long count_coprime(int n, int x) { // 1..n 中與 x 互質的數
    if (x == 1) return n;
    const auto &pf = prime_factors[x];
    int k = pf.size();
    long long not_coprime = 0;
    for (int mask = 1; mask < (1 << k); ++mask) {
        long long prod = 1;
        int bits = 0;
        for (int i = 0; i < k; ++i)
            if (mask & (1 << i)) prod *= pf[i], bits++;
        long long cnt = n / prod;
        if (bits & 1) not_coprime += cnt;
        else not_coprime -= cnt;
    }
    return n - not_coprime;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    linear_sieve();
    
    int T; cin >> T;
    while (T--) {
        int m, n; cin >> m >> n;
        if (m > n) swap(m, n); // 優化：遍歷較小維度
        long long ans = n; // x=1 貢獻
        for (int x = 2; x <= m; ++x)
            ans += count_coprime(n, x);
        cout << ans << "\n";
    }
    return 0;
}

複雜度分析

• 預處理：O(MAXN) 線性篩
• 單次查詢：∑ₓ₌₂ᵐ O(2ᵏˣ) ，kₓ 為 x 的不同質因子數（通常 ≤ 6）
• 最壞：m=100000，質因子最多 6 個 → 2⁶=64 子集
• 總操作數 ≈ 100000 × 32 ≈ 320 萬，極快

優化技巧

1. 交換 m,n：遍歷較小維度作為外層循環
2. 預計算質因子：線性篩同時記錄去重質因子
3. 位掩碼枚舉子集：高效實現容斥原理

數學等價形式

答案也等於：∑ₓ₌₁ᵐ φ(x) × ⌊n/x⌋ + 修正項（處理不完整塊）。但容斥法更直觀易實現。

樣例驗證

m=1, n=1: (1,1) gcd=1 → 1
m=2, n=3: (1,1)(1,2)(1,3)(2,1)(2,3) gcd=1 → 5

此題是數論中互質計數的經典應用，展示了線性篩+容斥原理的標準組合拳。