本文主要是介绍HDU 2841 Visible Trees 容斥，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意（一开始也没怎么看懂）：
一个人站在（0，0）处，树从（1，1）点开始排，共有m*n棵。如果两棵树在同一视线上（意思是两个点和（0，0）的斜率相同），则只看到前面一棵树，问你那个人能看到几棵树。
思路：
容斥。
简单分析之后，其实本质就是让你求gcd(x,y)=1有几组。（x，y）和（y，x）算两种。
这题和HDU 1695差不多，只不过那题（x，y）和（y，x）算一种。
1.先把<=1e5的每个数的质因子求出来并保存。
2.枚举x（1~m），对x的质因子进行容斥（在区间[1，n]中，对于x的某个质因子a，则可以知道有n/a个值和x是不互质的。因此对质因子容斥操作）。
3.累加每次枚举的结果。
枚举x容斥过程：
1.加上1个质因子集合的个数。
2.减去2个质因子集合的个数。
3.加上3个质因子集合的个数。
………………
code：
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;typedef long long LL;
const int MAXN = 1e5+5;
bool vis[MAXN];
vector<int> vec[MAXN];int x, y;
void get_prime()
{memset(vis, false, sizeof(vis));for(int i = 2;i < MAXN; i++){if(!vis[i]){vec[i].push_back(i);for(int j = i+i; j < MAXN ; j += i){vis[j] = true;vec[j].push_back(i);}}}
}
LL calc(int t, int p)
{int v = 1, cot = 0;LL ret = 0;for(int i = 0;i < vec[t].size(); i++){if(p&(1<<i)){v *= vec[t][i];cot++;}}ret = y/v;if(cot%2 == 0) ret = -ret;return ret;
}
void solve()
{LL res = 0;for(int i = 1;i <= x; i++){res += y;for(int j = 1;j < (1<<vec[i].size()); j++)res -= calc(i, j);}printf("%I64d\n", res);
}int main()
{get_prime();int T;scanf("%d", &T);while(T--){scanf("%d%d", &x, &y);solve();}return 0;
}
这篇关于HDU 2841 Visible Trees 容斥的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
