hdu 4135 Co-prime(容斥)

Co-prime

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2307 Accepted Submission(s): 861

Problem Description

Given a number N, you are asked to count the number of integers between A and B inclusive which are relatively prime to N. Two integers are said to be co-prime or relatively prime if they have no common positive divisors other than 1 or, equivalently, if their greatest common divisor is 1. The number 1 is relatively prime to every integer.

Input

The first line on input contains T (0 < T <= 100) the number of test cases, each of the next T lines contains three integers A, B, N where (1 <= A <= B <= 10¹⁵) and (1 <=N <= 10⁹).

Output

For each test case, print the number of integers between A and B inclusive which are relatively prime to N. Follow the output format below.

Sample Input

2
1 10 2
3 15 5

Sample Output

Case #1: 5
Case #2: 10
Hint

In the first test case, the five integers in range [1,10] which are relatively prime to 2 are {1,3,5,7,9}.

Source

The Third Lebanese Collegiate Programming Contest

题意：求A到B之间的数有多少个与n互质。

首先转化为（1---B）与n互质的个数减去（1--- A-1）与n互质的个数

然后就是求一个区间与n互质的个数了，注意如果是求（1---n）与n互质的个数，可以用欧拉函数，但是这里不是到n，所以无法用欧拉函数。

这里用到容斥原理，即将求互质个数转化为求不互质的个数，然后减一下搞定。

求互质个数的步骤：

1、先将n质因数分解

2、容斥原理模板求出不互质个数ans

3、总的个数减掉不互质个数就得到答案

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<set>
 5 #include<vector>
 6 using namespace std;
 7 #define ll long long
 8 #define N 1000000
 9 ll A,B,n;
10 vector<ll> v;
11 ll solve(ll x,ll n)
12 {
13     v.clear();
14     for(ll i=2;i*i<=n;i++) //对n进行素数分解
15     {
16         if(n%i==0)
17         {
18             v.push_back(i);
19             while(n%i==0)
20                n/=i;
21         }
22     }
23     if(n>1) v.push_back(n);
24     
25     ll ans=0;
26     for(ll i=1;i<( 1<<v.size() );i++)//用二进制来1,0来表示第几个素因子是否被用到,如m=3，三个因子是2,3,5，则i=3时二进制是011，表示第2、3个因子被用到
27     {
28         ll sum=0;
29         ll tmp=1;
30         for(ll j=0;j<v.size();j++)
31         {
32             if((1<<j)&i) //判断第几个因子目前被用到 
33             {
34                 tmp=tmp*v[j];
35                 sum++;
36             }
37         }
38         if(sum&1) ans+=x/tmp;//容斥原理，奇加偶减
39         else ans-=x/tmp;
40     }
41     return x-ans;
42 }
43 int main()
44 {
45     int t;
46     int ac=0;
47     scanf("%d",&t);
48     while(t--)
49     {
50         scanf("%I64d%I64d%I64d",&A,&B,&n);
51         printf("Case #%d: ",++ac);
52         printf("%I64d
",solve(B,n)-solve(A-1,n));
53     }
54     return 0;
55 }

View Code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define ll long long
 6 #define N 1000000
 7 ll A,B,n;
 8 ll fac[N];
 9 ll solve(ll x,ll n)
10 {
11     ll num=0;
12     for(ll i=2;i*i<=n;i++)
13     {
14         if(n%i==0)
15         {
16             fac[num++]=i;
17             while(n%i==0)
18                n/=i;
19         }
20     }
21     if(n>1) fac[num++]=n;
22     
23     ll ans=0;
24     for(ll i=1;i<(1<<num);i++)
25     {
26         ll sum=0;
27         ll tmp=1;
28         for(ll j=0;j<num;j++)
29         {
30             if((1<<j)&i)
31             {
32                 tmp=tmp*fac[j];
33                 sum++;
34             }
35         }
36         if(sum&1) ans+=x/tmp;
37         else ans-=x/tmp;
38     }
39     return x-ans;
40 }
41 int main()
42 {
43     int t;
44     int ac=0;
45     scanf("%d",&t);
46     while(t--)
47     {
48         scanf("%I64d%I64d%I64d",&A,&B,&n);
49         printf("Case #%d: ",++ac);
50         printf("%I64d
",solve(B,n)-solve(A-1,n));
51     }
52     return 0;
53 }

View Code