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 15) and (1 <=N <= 10 9).
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}.
题意：给出一个区间【L，R】，问在区间内，有多少数和数字N互质。
题解：因为区间很大，是1e15以内的数，要对每个数判断是否互质是不可能的，而N值也达到了1e9，暴力直接GG。因此我们考虑容斥原理来优化。
首先我们要求互质的数，可以用区间R-L+1个数减去非互质的数得到。
那么非互质的数怎么求。我们可以根据质因子得到。
对于区间L到R内的与N非互质的数，我们可以先求出【1，L】和【1，R】两区间内和N非互质的数。然后用【1，R】-【1，L】可以得到【L，R】内的所有与N互质的数。
求出N的质因子后，用区间边界L和R除以每个质因子，可以得到在区间1,R内能整除该因子的数的个数。
例如m = 12，n = 30的情况。
30的素因子数为2、3、5。
[1，12]中含有2的倍数的有：(2、4、6、8、10、12) = n/2 = 6个
[1，12]中含有3的倍数的有：(3、6、9、12) = n/3 = 4个
[1，12]中含有5的倍数的有：(5、10) = n/5 = 2个
这样求出的非互质因子个数肯定是有重复的。因此可以用到了容斥原理公式来减去重复的情况。
当得到的数的个数是奇数时，加上这个数量，是偶数时减去这个数量。
关于如何实现，首先我们已经求出了数N有cnt个质因子，对于cnt个质因子，可以单个出现，可以多个组合出现，共有2^cnt次方种选择方式，即，我们遍历2^cnt种情况，每种情况可以用一个二进制表示，如情况3即11，情况9即1001表示第一个素因子和第四个素因子组合在一起形成新的因子。这样用素因子组合得到所有因子。然后用给出的边界m除以每一个因子得到个数，根据个数判断是加上还是减掉。
这样求和后的ans即1到m区间内所有非重复的与N非互质的数的数量。用此方法求出【L,R】区间内非互质数的数量，再用R-L+1减去即最终结果，互质的数的数量。注意计算左区间时，L被包含在区间内，因此我们减去的是L-1，也就是-L+1，在查询时也是如此。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL pri[3090],cnt;
void broken(LL num)///分解质因数
{
cnt=0;
for(int i=2; i*i<=num; i++)
{
if(num%i==0)
{
pri[cnt++]=i;
while(num%i==0)num/=i;
}
}
if(num!=1)pri[cnt++]=num;
}
LL all(LL m)///容斥原理
{
LL ans=0;
for(int i=1;i<(1<<cnt);i++)
{
int sum=1,num1=0,tmp=i;
for(int j=0;j<cnt;j++)
{
if(1&tmp)
{
sum*=pri[j];
num1++;
}
tmp>>=1;
}
if(num1&1)ans+=m/sum;
else ans-=m/sum;
}
return ans;
}
int main()
{
int t,cas=1;
LL a,b,n;
scanf("%d",&t);
while(t--)
{
scanf("%lld%lld%lld",&a,&b,&n);
broken(n);
// printf("%lld %lld
",all(b),all(a));
printf("Case #%d: %lld
",cas++,b-all(b)-((a-1)-all(a-1)));
}
}