题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1695
题意：因为题目已经说明固定a=1，c=1，所以就是x在[1,b]，y在[1,d]，求有多少对(x,y)满足gcd(x,y)=k；(gcd指的是求俩数的最小公倍数)。
求解方式：一共有两种：一个是用容斥原理+欧拉函数，一个是莫比乌斯反演，在这我们用的是容器定理+欧拉函数，莫比乌斯反演我会另开一篇文章来讲。
先来说一下欧拉函数。欧拉函数用phi(n)表示（应该是φ(n)，但φ的读音就是phi，在这就用phi表示φ），phi(n)表示小于n的数中有phi(n)个数与n互质。
欧拉函数通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),
再来说一下容斥原理。公式：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
using namespace std;
long long a,b,c,d,k;
/*素数筛选和合数分解*/
const int maxn=100100;
int prime[maxn+1];
void getprime(){
memset(prime,0,sizeof(prime));
for(int i=2;i<maxn;i++){
if(!prime[i]) prime[++prime[0]]=i;
for(int j=1;j<=prime[0]&&prime[j]<=maxn/i;j++){
prime[prime[j]*i]=1;
if(i%prime[j]==0) break;
}
}
}
/*合数分解*/
long long factor[105][2];
int fatcnt;
int getfactor(long long x){
if(x==0)
return 0;
fatcnt=0;
long long tmp=x;
for(int i=1;prime[i]<=tmp/prime[i];i++){
factor[fatcnt][1]=0;
if(tmp%prime[i]==0){
factor[fatcnt][0]=prime[i];
while(tmp%prime[i]==0){
factor[fatcnt][1]++;
tmp/=prime[i];
}
fatcnt++;
}
}
if(tmp!=1){
factor[fatcnt][0]=tmp;
factor[fatcnt++][1]=1;
}
return fatcnt;
}
/*欧拉函数筛*/
int phi[100100];
void phitable_ZY(int n){
memset(phi,0,sizeof(phi));
phi[1]=1;
for(int i=2;i<=n;i++) if(!phi[i])
for(int j=i;j<=n;j+=i){
if(!phi[j]) phi[j]=j;
phi[j]=phi[j]/i*(i-1);
}
}
long long cr(long long i){
getfactor(i);
long long ans=0;
for(int i=1;i<(1<<fatcnt);i++){
long long t=1;
int cut=0;
for(int j=0;j<fatcnt;j++){
if(i&(1<<j))
t*=factor[j][0],cut++;
}
if(cut&1)
ans+=b/t;
else
ans-=b/t;
}
return (long long)b-ans;
}
int main(){
getprime();
phitable_ZY(100010);
int t,cas=0;
scanf("%I64d",&t);
while(t--){
scanf("%I64d%I64d%I64d%I64d%I64d",&a,&b,&c,&d,&k);
printf("Case %d: ",++cas);
if(k==0||k>b||k>d){
printf("0\n");
continue;
}
b/=k;
d/=k;
long long ans=0;
if(b>d)
swap(b,d);
for(int i=1;i<=b;i++)
ans+=phi[i];
for(int i=b+1;i<=d;i++){
ans+=cr(i);
}
printf("%I64d\n",ans);
}
return 0;
}
原文：http://blog.csdn.net/wangzhen_yu/article/details/44567179