hdu-2841 Visible Trees---容斥定理

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=2841

题目大意：

N*M的格点上有树，从0，0点可以看到多少棵树。

解题思路：

发现如果A1/B1=A2/B2那么就有一棵树看不到，所以就是找出Ai/Bi有多少种。

如果A,B有大于1的公约数，则A=A'*D B=B'*D，那么A/B=A'/B',也就是存在另外一组数和这种相等，则问题转换成有多少对互质的数。

求1-m中有多少个与1-n中互质的数目，

可以枚举m，每次求1-n中与m互质的数目。（HDU-4135简单版）

初始化：m = 1的时候，答案就是n

 1 #include<iostream>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 1e6 + 10;
 5 ll a[50], tot;
 6 ll gcd(ll a, ll b)
 7 {
 8     return b == 0 ? a : gcd(b, a % b);
 9 }
10 void init(ll n)//求出n的素因子
11 {
12     tot = 0;
13     for(ll i = 2; i * i <= n; i++)
14     {
15         if(n % i == 0)
16         {
17             a[tot++] = i;
18             while(n % i == 0)n /= i;
19         }
20     }
21     if(n != 1)a[tot++] = n;
22 }
23 ll sum(ll m)//求[1, m]中与n互质的个数
24 {
25     ll ans = 0;
26     for(int i = 1; i < (1 << tot); i++)//a数组的子集
27     {
28         ll num = 0;
29         for(int j = i; j; j >>= 1)if(j & 1)num++;//统计i的二进制中1的个数
30         ll lcm = 1;
31         for(int j = 0; j < tot; j++)
32             if((1 << j) & i)
33         {
34             lcm = lcm / gcd(lcm, a[j]) * a[j];
35             if(lcm > m)break;
36         }
37         if(num & 1)ans += m / lcm;//奇数加上
38         else ans -= m / lcm;//偶数减去
39     }
40     return m - ans;
41 }
42 ll n, m;
43 int main()
44 {
45     int T, cases = 0;
46     cin >> T;
47     while(T--)
48     {
49         cin >> n >> m;
50         //if(n < m)swap(n, m);
51         ll ans = n;
52         for(int i = 2; i <= m; i++)
53         {
54             init(i);
55             ans += sum(n);
56         }
57         cout<<ans<<endl;
58     }
59     return 0;
60 }