<題目連結>
題目大意：
給定區間[A,B](1 <= A <= B <= 10 15)和N(1 <=N <= 10 9)，求出該區間中與N互質的數的個數。
解題分析：
将求區間[A,B]與N互質的數轉化成求[1,B] 區間與N互質的個數 - [1,A-1]中與N互質的個數。同時，因為直接求區間内與N互質的數不好求，我們從反面入手，求出與N不互質的數，借鑒埃篩的思想，我們先求出N的所有質因子，然後将這些質因子在區間内倍數的個數全部求出(即與N不互質的數)，再用區間的總數減去這些不互質數的個數即可。但是，由于在求不互質的數的時候，存在重複的計算，是以我們利用容斥對重複計算的數進行處理。容斥處理有多重表現形式，DFS、隊列、位運算均可進行容斥處理。
得到一個數的所有質因子：
for(ll i=2;i*i<=m;i++)
if( m%i==0){ //得到m的所有的素因子
vec.push_back(i);
while(m%i==0)m/=i;
}
if(m>1)vec.push_back(m); 位運算：
1 #include <cstdio>
2 #include <cstring>
3 #include <vector>
4 #include <algorithm>
5 using namespace std;
6
7 typedef long long ll;
8 vector<ll>vec;
9 ll a,b,n;
10
11 ll solve(ll x,ll m){ //[1,x]區間内與m4互質的數的個數
12 vec.clear();
13 for(ll i=2;i*i<=m;i++) if( m%i==0){ //得到m的所有的素因子
14 vec.push_back(i);
15 while(m%i==0)m/=i;
16 }
17 if(m>1)vec.push_back(m);
18 ll sum=0,val,cnt;
19 for(ll i=1;i<(1<<vec.size());i++){ //枚舉所有素因子的乘積組合,用二進制表示哪幾個因子被用到
20 val=1,cnt=0;
21 for(ll j=0;j<vec.size();j++){
22 if(i & (1<<j)) { //因為vec裡全為質數，是以它們進行組合的時候，直接相乘就行，而不用求lcm
23 val*=vec[j],cnt++; //cnt表示目前相乘因子的個數，用于後面容斥時進行加減的判斷
24 }
25 }
26 //容斥，奇加偶減
27 if(cnt & 1)sum+=x/val; // x/tval為[1,x]内為tval的倍數的數的個數
28 else sum-=x/val;
29 }
30 return x-sum; //[1,x]的總數減去1~X中各素數倍數的總數
31 }
32
33 int main(){
34 int T,ncase=0;scanf("%d",&T);while(T--){
35 scanf("%lld%lld%lld",&a,&b,&n);
36 ll ans=solve(b,n)-solve(a-1,n);
37 printf("Case #%d: %lld\n",++ncase,ans);
38 }
39 }