首先發出題目連結：
連結：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;
}