HDU 2841：Visible Trees ← 容斥原理

【题目来源】
http://acm.hdu.edu.cn/showproblem.php?pid=2841

【题目描述】
There are many trees forming a m * n grid, the grid starts from (1,1). Farmer Sherlock is standing at (0,0) point. He wonders how many trees he can see.
If two trees and Sherlock are in one line, Farmer Sherlock can only see the tree nearest to him.

【输入格式】
The first line contains one integer t, represents the number of test cases. Then there are multiple test cases. For each test case there is one line containing two integers m and n(1 ≤ m, n ≤ 100000)

【输出格式】
For each test case output one line represents the number of trees Farmer Sherlock can see.

【输入样例】
2
1 1
2 3

【输出样例】
1
5

【算法分析】
在计数时，必须注意无一重复，无一遗漏。为了使重叠部分不被重复计算，人们研究出一种计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。

针对本题，显然，若 (x,y) 能被看到，那么 (k*x, k*y) 都不能被看到（其中，k>1）。
因此，问题转化为求 1<=x<=n 且 1<=y<=m 有多个 <x,y> 满足 gcd(x,y)=1。
那么可以从 1～n 枚举 x，累计 1～m 中与 x 互质的个数。
对 x 分解素因子，容斥一下就可得到结果。

【算法代码】

#include <iostream>
#include <vector>
using namespace std;

typedef long long LL;
vector<int> v;
int n,m;

void pfac(int x) { //Find all the prime factors of x
    v.clear();
    for(int i=2; i*i<=x; i++) {
        if(x%i==0) {
            v.push_back(i);
            while(x%i==0) x/=i;
        }
    }
    if(x>1) v.push_back(x);
}

int solve(int x) {
    int sum=0;
    for(int i=1; i<(1<<v.size()); i++) {
        int res=1,cnt=0;
        for(int j=0; j<v.size(); j++) {
            if(i & (1<<j)) {
                res*=v[j];
                cnt++;
            }
        }
        if(cnt & 1) sum+=x/res;
        else sum-=x/res;
    }
    return sum;
}

int main() {
    int T;
    cin>>T;
    while(T--) {
        scanf("%d %d",&n,&m); //cin>>n>>m;
        LL ans=m;
        for(int i=2; i<=n; i++) {
            pfac(i);
            ans+=m-solve(m);
        }
        printf("%lld\n",ans);
    }
}


/*
in:
2
1 1
2 3

out:
1
5
*/

【参考文献】
https://www.cnblogs.com/00isok/p/10358598.html
https://blog.csdn.net/weixin_53746961/article/details/121175561
https://blog.csdn.net/weixin_43846139/article/details/105517437
https://www.cnblogs.com/crackpotisback/p/4846909.html
http://www.manongjc.com/detail/39-wpncookuuhcoyui.html
https://blog.csdn.net/weixin_30710457/article/details/98919034