Co-prime

Co-prime
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 121    Accepted Submission(s): 56




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 <= 1015) and (1 <=N <= 109).
 


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
 


Recommend
lcy


//开始系统的学习容斥原理！通常我们求１～ｎ中与ｎ互质的数的个数都是用欧拉函数！　但如果ｎ比较大或者是求１～ｍ中与ｎ互质的数的个数等等问题，
要想时间效率高的话还是用容斥原理！
容斥原理示例；（A∪B∪C = A+B+C - A∩B - B∩C - C∩A + A∩B∩C）


//本题是求[a,b]中与n互质的数的个数，可以转换成求[1,b]中与n互质的数个数减去[1,a-1]与n互质的数的个数。可先求[1,n]中与数m有公约数的个数k,则n-k即为互素个数
第一步：先求m的素因子表，模板为：
  for(i=2;i*i<=n;i++) //对n进行素因子分解   
            if(n&&n%i==0)  
            {  
                prime[m++]=i;  
                while(n&&n%i==0)  
                    n/=i;  
            }  
而后构造函数求解k,prime[1],prime[2],prime[3]·····之间一个几个的乘积为temp，用m除以temp则可知道容斥中某个集合元素的个数，然后应用容斥定理即可，注意奇加偶减
ll  solve(ll num, int m)
{
    ll ans=0,temp,i,j,flag;
    for(i=1;i<ll(1<<m);i++)               //用二进制来1,0来表示第几个素因子是否被用到,如m=3，三个因子是2,3,5，则i=3时二进制是011，表示第2、3个因子被用到   
    {  
    {
        temp=1,flag=0;
        for(j=0;j<m;j++)
            if(i&(ll(1<<j)))
            flag++,temp*=prime[j];       //该处循环是判断第几个因子目前被用到   
        if(flag&1)
            ans+=num/temp;
        else ans-=num/temp;              //容斥原理，奇加偶减   
    }
    return ans;
}




完整代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef  long long  ll;
#define maxn 70
ll prime[maxn];
ll  solve(ll num, int m)
{
    ll ans=0,temp,i,j,flag;
    for(i=1;i<ll(1<<m);i++)
    {
        temp=1,flag=0;
        for(j=0;j<m;j++)
            if(i&(ll(1<<j)))
            flag++,temp*=prime[j];
        if(flag&1)
            ans+=num/temp;
        else ans-=num/temp;
    }
    return ans;
}
int main()
{
    int T,t=0,m;
    ll n,a,b,i;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%I64d%I64d%I64d",&a,&b,&n);
        m=0;
        for(i=2;i<sqrt(n*1.0);i++)
        {
            if(n&&n%i==0)
            {
                prime[m++]=i;
                while(n&&n%i==0)
                    n/=i;
            }
        }
        if(n>1)
            prime[m++]=n;
        printf("Case #%d: %I64d\n",++t,(b-solve(b,m))-(a-1-solve(a-1,m)));
    }
    return 0;
}