hdu-4135 Co-prime---容斥定理经典&&求1-m中与n互质的数目

题目链接：

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

题目大意：

求区间[a, b]中与N互质的数目。

解题思路：

首先对n求出所有素因子。

对于区间[1, m]中，只需要对n素因子求出所有子集，就可以求出所有的与n不互质的数目num，那么互质的数就是m-num；

对于区间[a, b]，就等于[1, b]的数目 - [1，a - 1]的数目。

 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, l, r;
43 int main()
44 {
45     int T, cases = 0;
46     cin >> T;
47     while(T--)
48     {
49         cin >> l >> r >> n;
50         init(n);
51         cout<<"Case #"<<++cases<<": "<<sum(r) - sum(l - 1)<<endl;
52     }
53     return 0;
54 }