首先发出题目链接：
链接：https://ac.nowcoder.com/acm/contest/634/C
来源：牛客网
涉及：容斥定理，gcd及扩展gcd
题目如下：
一般来说看到这种gcd数学题看到数据范围折磨大就知道肯定有技巧！然而这个题真的有技巧。
要知道，题目意思是让我们在区间[L+K,R-K]里面找出所有y的个数，使得y+k和y-k互质
这个问题看似只能用暴力，但是其实可以把这个问题等价代换一下，变成：
让我们在区间[L,R-2K]里面找到所有y的个数，使得y和y+2k互质。
即 g c d ( y , y + 2 ∗ k ) = 1 gcd(y,y+2*k)=1 gcd(y,y+2∗k)=1
而 g c d ( y , y + 2 ∗ k ) = 1 gcd(y,y+2*k)=1 gcd(y,y+2∗k)=1又可以变成 g c d ( y , 2 ∗ k ) = 1 gcd(y,2*k)=1 gcd(y,2∗k)=1
因此最后问题变成了
让我们在区间[L,R-2K]里面找到所有y的个数，使得y和2k互质，所以对于y来说，y的取值范围就是[L,R-2K]，可以在开始就把R-2K赋给R。
特判：如果R-2*K<L，则答案为0；
要是y和2k互质，则y和2k的最大公约数只能为1
根据可知，所有的正整数都可以化为n个素数的乘积，因此们可以把2k分解质因子，得到2k的所有质因子，然后求出[L,R-2K]所有的质因子的倍数的个数x，然后用区间的长度减去x，得到的就是区间内和2k互质的数的个数
而求出k的所有质因子的个数，可以用容斥定理来求得
容斥定理：
( A 1 ∪ A 2 ∪ A 3 ∪ . . . ∪ A n ) = ∑ 0 < i ≤ n A i − ∑ 0 < i < j ≤ n ( A i ∩ A j ) + ∑ 0 < i < j < k ≤ n ( A i ∩ A j ∩ A j ) + . . . + ( − 1 ) n + 1 ( A 1 ∩ A 2 ∩ A 3 ∩ . . . ∩ A n ) (A_{1} \cup A_{2} \cup A_{3} \cup ... \cup A_{n})=\sum_{0<i\le n} A_{i}-\sum_{0<i<j\le n} (A_{i} \cap A_{j})+\sum_{0<i<j<k\le n}(A_{i}\cap A_{j}\cap A_{j})+...+(-1)^{n+1}(A_{1} \cap A_{2}\cap A_{3}\cap ... \cap A_{n}) (A1∪A2∪A3∪...∪An)=0<i≤n∑Ai−0<i<j≤n∑(Ai∩Aj)+0<i<j<k≤n∑(Ai∩Aj∩Aj)+...+(−1)n+1(A1∩A2∩A3∩...∩An)
将2k分解质因子
由于k的数据范围小于1013,分解出来的质数顶多也就12个左右，可以用暴力求得k的所有质数
先将2k的值赋给k，然后i从2开始往上找，是i的因数那就只可能i是质数，然后while循环k除以i，将i放到数组里备用，最后for循环结束之后，如果k大于1，此时的k也是原来2k的一个质因子，最后divisor数组里就存的是原来2k的所有质因子。
void resolve(){
int i;
k=2*k;
for(i=2;i*i<=k;i++){
if(k%i==0) divisor[tot++]=i;
while(k%i==0) k/=i;
}
if(k!=1) divisor[tot]=k;
return;
}
容斥定理
容斥定理偶数个集合交集就是容，奇数个集合交集就是斥
集合交集就是多个质因子相乘后的数的倍数的个数（质因子互质，最小公倍数就是相乘）
void dfs(ll p,ll x,ll mu,bool ok){
if(ok && x) sum+=mu*(r/x-(l-1>=0?l-1:0)/x);
if(p==tot+1) return;
dfs(p+1,x,mu,false);
dfs(p+1,x*divisor[p],-mu,true);
return;
}
容斥定理可以用递归来实现
当最小公倍数是偶数个质因子相乘即是斥，反之则容
每个质因子可以考虑乘以当前的公倍数得到新的公倍数，也可以不乘。
dfs(ll p,ll x,ll mu,bool ok)
其中p是考虑第p-1个质因子是否与当前公倍数相乘；
x是当前的公倍数（开始递归的时候x要取1，ok要取false）；
mu是判断容斥；
ok是防止重复计算（当考虑到某个质因子不与当前公倍数相乘，则下次递归x未发生变化，就不用再次计算此公倍数的倍数在区间内的个数）
计算当前公倍数的倍数在区间内的个数是 s u m + = m u ∗ ( r / x − ( l − 1 ) / x ) sum+=mu*(r/x-(l-1)/x) sum+=mu∗(r/x−(l−1)/x)（L是原来的l减去了2k）
（r/x是1到r内x的倍数的个数，（l-1）是1到（l-1）内公倍数的个数，两个相减就是区间内x倍数的个数）
ps：这个式子只能当L和R大于1时候成立，不然个数就少算了一个（不行你可以去试一试）
还要注意一点，由于L的数据范围是大于等于0，而0与任何数的最小公因数是这个数本身，由于1不是质数，所以如果输入的L是等于0的话，sum少算了一个数0，最终sum要加上1；
因此，就求个数的式子应该是
m u ∗ ( r / x − ( l − 1 > = 0 ? l − 1 : 0 ) / x ) mu*(r/x-(l-1>=0?l-1:0)/x) mu∗(r/x−(l−1>=0?l−1:0)/x)，当L为0时，L-1要仍然为0；
递归结束后，答案就是区间长度减去sum（sum是区间内与2k不互质数的个数）
r − l + 1 − ( s u m + ( l = = 0 ? 1 : 0 ) ) r-l+1-(sum+(l==0?1:0)) r−l+1−(sum+(l==0?1:0))（当L为0时，最终sum要加上1）
日常举例子
就举0 20 6这个例子
首先将6分解质因子
分解出2和3
l=0,r=r-2*k=8
开始dfs(1,1,-1,false)//dfs(ll p,ll x,ll mu,bool ok)
1.在dfs(1,1,-1,false)中，ok等于false，跳过中间步骤
下一下语句是dfs(2,1,-1,false)和dfs(2,2,1,true)
1.1在dfs(2,1,-1,false)中，ok等于false，跳过中间步骤
下一条语句是dfs(3,1,-1,false)和dfs(3,3,-1,true)
1.1.1在dfs(3,1,-1,false)中，ok等于false，跳过中间步骤
下一条语句是if(p==tot+1) return;
终止递归（tot是质因子的数量，tot=2）
1.1.2在dfs(3,3,-1,true)中，ok等于true
此时sum=0，计算sum+=mu*(r/x-(l-1>=0?l-1:0)/x);
（求8以内3的倍数个数，算出结果为8/3=2，此时sum=2）
下一条语句是if(p==tot+1) return;
终止递归
1.2在dfs(2,2,1,true)中，ok等于true
此时sum=2，计算sum+=mu*(r/x-(l-1>=0?l-1:0)/x);
（求8以内2的倍数个数，算出结果为8/2=4，此时sum=6）
下一条语句是dfs(3,2,1,false)和dfs(3,6,-1,true)
1.2.1在dfs(3,2,1,false)中，ok等于false，跳过中间步骤
下一条语句是if(p==tot+1) return;
终止递归（tot是质因子的数量，tot=2）
1.2.2在dfs(3,6,-1,true)中，ok等于true
此时sum=6，计算sum+=mu*(r/x-(l-1>=0?l-1:0)/x);
（求8以内6的倍数个数，算出结果为8/6=1，此时sum=5）
下一条语句是if(p==tot+1) return;
终止递归（tot是质因子的数量，tot=2）
最终sum=5，由于L=0，sum=sum+1=6；
答案为r-l+1-sum=8-0+1-6=3
代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll l,r,k,tot=1;//l和r以及k是题目数据，tot是k的质因子的种类个数
ll divisor[25]={0};//这个数组存k的质因子
ll sum=0;
void resolve(){//k分解质因子函数
int i;
for(i=2;i*i<=k;i++){
if(k%i==0) divisor[tot++]=i;
while(k%i==0) k/=i;//防止重复算质因子
}
if(k!=1) divisor[tot]=k;//最后的k如果不为0，也仍然是一个质因子
return;
}
void dfs(ll p,ll x,ll mu,bool ok){//容斥定理
if(ok && x) sum+=mu*(r/x-(l-1>=0?l-1:0)/x);
if(p==tot+1) return;//所有质因子全部被考虑到就返回
dfs(p+1,x,mu,false);//不选择divisor[p]乘当前公倍数x，则x不变，下次递归跳过计算步骤
dfs(p+1,x*divisor[p],-mu,true);//选择divisor[p]乘当前公倍数x，则x变化，下次递归以新的x再次计算x的倍数在区间的个数
return;
}
int main(){
cin>>l>>r>>k;
r-=2*k;
if(l>r) return !(cout<<"0");//特判
k=2*k;
resolve();
dfs(1,1,-1,false);//从第一个质因子开始考虑，x此时为1，令mu=-1，由于x=1时不知质因子公倍数，所以不进行计算
cout<<r-l+1-(sum+(l==0?1:0));//如果l为0，则sum要加上1（要考虑特殊数字0）
return 0;
}