题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4135
Co-prime
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1176 Accepted Submission(s): 427
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.
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
1 10 2
3 15 5
Sample Output
Case #1: 5
Case #2: 10
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
Recommend
lcy
题目意思：
给一个a,b,n求在[a,b]内有多少个与n互质的数。
解题思路：
简单的容斥原理。
反面思考。先求出与n不互质的，也就是包括n的质因数的。然后就能够想到先把n分解质因数。
然后能够想到先预处理1000000内的质数。
然后求出1~b满足要求的个数，减去1~a-1满足要求的个数，答案即为最后结果。
代码：
//#include<CSpreadSheet.h>
#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#include<cmath>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll __int64
#define LL long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#define M 1000000007
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
#define N 1000000
int prime[130000],cnt;
bool isprime[N+10];
int pp[110000],cnt0;
ll a,b,n,ans1,ans2;
void init() //预处理出1~1000000内的质数
{
cnt=0;
for(int i=1;i<=N;i++)
isprime[i]=true;
for(int i=2;i<=N;i++)
{
if(!isprime[i])
continue;
prime[++cnt]=i;
for(int j=i*2;j<=N;j+=i)
isprime[j]=false;
}
//printf("cnt:%d\n",cnt);
}
void Cal(ll cur) //分解出cur的质因数
{
cnt0=0;
for(int i=1;prime[i]*prime[i]<=cur;i++)
{
if(cur%prime[i]==0)
{
pp[++cnt0]=prime[i];
while(!(cur%prime[i]))
cur/=prime[i];
}
}
if(cur!=1)
pp[++cnt0]=cur;
}
void dfs(ll hav,int cur,int num) //容斥原理求出互质的
{
if(cur>cnt0||(hav>a&&hav>b))
return ;
for(int i=cur;i<=cnt0;i++)
{
ll temp=hav*pp[i];
if(num&1)
{
ans1-=b/temp;
ans2-=a/temp;
}
else
{
ans1+=b/temp;
ans2+=a/temp;
}
dfs(temp,i+1,num+1);
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
init();
//system("pause");
int t;
scanf("%d",&t);
for(int ca=1;ca<=t;ca++)
{
scanf("%I64d%I64d%I64d",&a,&b,&n);
Cal(n);
//printf("cnt0:%d\n",cnt0);
a--;
ans1=b,ans2=a;
for(int i=1;i<=cnt0;i++)
{
ans1-=b/pp[i];
ans2-=a/pp[i];
dfs(pp[i],i+1,2);
}
printf("Case #%d: %I64d\n",ca,ans1-ans2);
}
return 0;
}