<题目链接>
题目大意：
给定区间[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=;i*i<=m;i++)
if( m%i==){ //得到m的所有的素因子
vec.push_back(i);
while(m%i==)m/=i;
}
if(m>)vec.push_back(m);
位运算：
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std; typedef long long ll;
vector<ll>vec;
ll a,b,n; ll solve(ll x,ll m){ //[1,x]区间内与m4互质的数的个数
vec.clear();
for(ll i=;i*i<=m;i++) if( m%i==){ //得到m的所有的素因子
vec.push_back(i);
while(m%i==)m/=i;
}
if(m>)vec.push_back(m);
ll sum=,val,cnt;
for(ll i=;i<(<<vec.size());i++){ //枚举所有素因子的乘积组合,用二进制表示哪几个因子被用到
val=,cnt=;
for(ll j=;j<vec.size();j++){
if(i & (<<j)) { //因为vec里全为质数，所以它们进行组合的时候，直接相乘就行，而不用求lcm
val*=vec[j],cnt++; //cnt表示当前相乘因子的个数，用于后面容斥时进行加减的判断
}
}
//容斥，奇加偶减
if(cnt & )sum+=x/val; // x/tval为[1,x]内为tval的倍数的数的个数
else sum-=x/val;
}
return x-sum; //[1,x]的总数减去1~X中各素数倍数的总数
} int main(){
int T,ncase=;scanf("%d",&T);while(T--){
scanf("%lld%lld%lld",&a,&b,&n);
ll ans=solve(b,n)-solve(a-,n);
printf("Case #%d: %lld\n",++ncase,ans);
}
}
2019-02-09