HDU 2841 Visible Trees：容斥原理計算可見格子數

題目

n×m 格子，農夫在 (0,0) 觀察，視線被最近格子擋住。求可見格子數。即統計有多少對 (x,y) (1≤x≤n, 1≤y≤m) 滿足 gcd(x,y)=1，再加上 x=0 或 y=0 的情況（共 n+m+1 個軸上點，但 (0,0) 不算）。

容斥原理

對固定 x，在 [1,m] 中與 x 互質的 y 的個數 = m - Σ_{p|x} m/p + Σ_{p

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100010;
vector primeFactors[MAXN];
bool isCompo[MAXN];

void sieve() {
    for (int i = 2; i < MAXN; i++) {
        if (!isCompo[i]) {
            for (int j = i; j < MAXN; j += i)
                primeFactors[j].push_back(i), isCompo[j] = true;
        }
    }
}

int dfs(int idx, int x, int limit) { // 返回 [1,limit] 中能被 x 的質因子整除的數的個數
    int res = 0;
    for (int i = idx; i < (int)primeFactors[x].size(); i++) {
        int p = primeFactors[x][i];
        res += limit / p - dfs(i+1, x, limit / p);
    }
    return res;
}

int main() {
    sieve();
    int T; scanf("%d", &T);
    while (T--) {
        int n, m; scanf("%d%d", &n, &m);
        ll ans = m; // x=0 時 y=1..m 共 m 個
        for (int x = 2; x <= n; x++)
            ans += m - dfs(0, x, m); // 互質數 = 總數 - 不互質數
        printf("%lld\n", ans);
    }
    return 0;
}