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}.
题解：
题意概括：
题意很简单，让你找从A到B之间与n互质的数的数目。（互质：两个数的最大公约数为1）
解题思路：
首先你应该把n的质因子求出来，因为n的质因子的倍数一定不是与n互质的数。利用容斥定理，把每个质因子及它的倍数当成一个集合。
只能选或不选，n个质因子的选法总共有多少种呢？二进制枚举告诉我们总共有2^n种，但是你必须要拿出一个质因子，所以从1开始，总共有2^n-1中选法，枚举每一种二进制数。枚举每一种二进制数的每一位，利用if(1&i>>j)找到是否选择第j个物品，如果选择，集合数+1。
然后判断集合数的奇偶，根据容斥定理偶加奇减的原则，如果是奇，则总数减去这个质因子集合，如果是偶，则总数加上这个质因子集合。
集合数的奇数倍或者偶数倍，就这道题而言，要变成两个质因子的乘积。
代码中为什么是SUM+=B/sum呢，因为如果你知道了一个质因子a，你要求在区间[1,n]内有多少是它的倍数的数，你就拿n/a，结果就是a的倍数的数量。例如，30中5的倍数的个数，30/5=6,5的倍数的数量就是6个。
因为这里是从A到B，而不是从1到B，所以当集合数为奇数时，总数要加上B/sum，再减去[1,A]中sum的倍数，也就是SUM-=(A-1)/sum。
注意代码中的SUM求得是所有质因子及其倍数的总数量，而sum求的是每个质因子或者相交集合时，几个质因子的乘积。
AC代码：
//#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn=105;
int prim[maxn]; //存每个N的质因子
int main()
{
// freopen("input.txt","r",stdin);
ll A,B,t,n;
cin>>t;
ll th=0;//记录测试数据的序号
while(t--)
{
th++;
memset(prim,0,sizeof prim);
scanf("%lld%lld%lld",&A,&B,&n);
ll num=0;//记录质因子的个数
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
{
num++;
prim[num]=i;
while(n%i==0)
{
n/=i;
}
}
}
if(n>1)
{
num++;
prim[num]=n;
}
ll SUM=0;
for(int i=1;i<(1<<num);i++)
{
ll cnt=0;//记录遍历每个二进制位数时的集合数
ll sum=1;//如果是单个集合数，表示质因子，如果是多个集合数，则是多个质因子相乘的结果
for(int j=0;j<num;j++)
{
if(1&(i>>j))
{
cnt++;
sum*=prim[j+1];
}
}
if(1&cnt)
{
SUM+=B/sum;
SUM-=(A-1)/sum;
}
else
{
SUM-=B/sum;
SUM+=(A-1)/sum;
}
}
printf("Case #%lld: %lld\n",th,B-A+1-SUM);
}
return 0;
}
参考了这个同学的代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define met(Q,QQ) memset(Q,QQ,sizeof(Q))
int main()
{
ll t,A,B,n,a[103];
scanf("%lld",&t);
ll aaa=0;
while(t--)
{
aaa++;
met(a,0);
scanf("%lld %lld %lld",&A,&B,&n);
ll cnt=0;
for(int i=2;i*i<=n;i++) //质因子分解
{
if(n%i==0)
{
cnt++;
a[cnt]=i;
}
while(n%i==0)
{
n/=i;
}
}
if(n!=1)
{
cnt++;
a[cnt]=n;
}
ll SUM=0;//SUM的目的是算所有不与n互质的数
for(int i=1;i<(1<<cnt);i++)//二进制枚举所有可能的值从1到2^n，i从1开始，所以是从1开始枚举
{
ll sum=1,cnt1=0;
for(int j=0;j<cnt;j++)//枚举的作用？枚举每一位，看是否选择了第j件物品
{
if(1&(i>>j)) //判断有没有选中这个集合,如何判断的？如果为1，则说明选中了这件物品
{
sum*=a[j+1]; //选中的数字的乘积，a[j+1]？sum*=a[j+1],如果只有一个质因子，则就等于这个质因子，如果有多个就乘起来，表示相交，之后用B除以他们的积
cnt1++;; //二进制中选中1的个数，选中这个集合的个数？
} //既然0、1表示选与不选，那么如果选了就+1，表示计数
}
if(cnt1&1) //个数为奇数的情况，如果那几个二进制位上的1相加为奇数，那就加上呗
{
SUM+=B/sum;//算出从1到B中能被sum整除掉的个数，即能被质因子除尽的数或者能被相交集合的质因子的乘积除尽的数，相交集合的时候就是除以两个质因子的乘积
SUM-=(A-1)/sum;//再减去从1到A中能被sum整除掉的个数就是从A到B中能被sum整除的个数
}
else//选中个数为偶数的情况
{
SUM-=B/sum;//与上面的相反咯
SUM+=(A-1)/sum;
}
}//最后得到的SUM是2、3、5集合并起来的值，即所有质因子及其质因子倍数的总数
printf("Case #%lld: %lld\n",aaa,B-A+1-SUM);
}
return 0;
}
// 把物品的选择与不选择想象成0和1
// 就这一题来说，就是把质因子的个数计数为n。
// 想象成有n个二进制位。第一个二进制位为2，第二个3，第三个5
// 用0,1来计数
// 0 0 1 表示选择了5
// 0 1 1 表示选择了3和5
涉及知识点：
1、左移运算符<<。
运算符左边是移位对象，右边是整型表达式，代表左移的位数，其功能是把“<<”左边的运算数的各二进制位全部左移若干位。高位丢弃，低位补0。
如果是1<<n的话，表达式的值就是2^n。
2、右移运算符与左移运算符相似。
3、按位与运算符&。
双目运算符，其功能是参与运算的两个运算对象的各对应二进制位分别进行“与”运算。只有对应的两个二进制位均为1时，结果位才为1，否则为0。参与运算的数以补码的方式出现。
给个栗子：9&(-5)
00000000 00001001 (9的二进制补码)
11111111 11111011 (-5的二进制补码)
00000000 00001001 (结果)
1 1
发现没有^_^,只有都为1的时候才等于1
按位与运算通常用来对某些位清0或保留某些位。
就像上面的代码那样1&(i>>j), 因为1的补码是0000 0001，所以表达式就成了取i>>j的末位。
4、给出求2^n的二进制码的代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;//一共n个物品；
scanf("%d",&n);
for(int i=0;i<(1<<n);i++)//从0到2的n次方-1；
{
for(int j=n-1;j>=0;j--) //判断第j个物品有没有被选中；
printf("%d ",1&(i>>j));//思考下为什么j到0结束呢，底部给出原因
printf("\n");
}
return 0;
}
因为i>>j是向左移j位，你每次要取i末尾的值，但是移位前的末尾值你也要取
所以索性就从0开始了
5、容斥定理，偶加奇减，即偶数倍个集合就加，奇数倍个集合就减。
此题参考了此博客：https://blog.csdn.net/qq_42757965/article/details/99060042