题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1695
题目解析：
Given 5 integers: a, b, c, d, k, you're to find x in a...b, y in c...d that GCD(x, y) = k.
题目又说a==c==1,所以就是求[1,b]与[1,d]中gcd等于k的个数，因为若gcd(x,y)==z,那么gcd(x/z,y/z)==1，又因为不是z的倍数的肯定不是，所以不是z的倍数的可以直接去掉，所以只要将b和d除以k，然后就转化成了求两个范围中互质的对数了。即求[1,b/k],与[1,d/k]中互质的数目，让b<d,又因为 (x=5, y=7) and (x=7, y=5) are considered to be the same.
所以先求[1,b/k]中互质的数目，即phi[1]+phi[2]+phi[3].....+phi[b/k]（其中phi[i]为i的欧拉函数值），再从区间[b/k+1,d/k]枚举与区间[1,b/k]中互质的数目。其中求与区间[1,b/k]中互质的数目可以通过容斥原理求得与区间[1,b/k]中不互质的数目，相减便可以求得结果。这题折腾了一中午，一直TLE，代码在后面贴了，之后看大神的博客知道了哪里超时的原因，每个数的质因子可以在打表求欧拉函数的时候顺便求出来，一种哈希的思想，这样就不用在枚举的时候每一个数在求一遍他的质因子了，好题！
代码如下：（608ms）
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <math.h>
using namespace std;
typedef __int64 ll;
ll sum,phi[];
int cnt[][],f[],a,b,c,d,x;
void init()
{
memset(f,,sizeof(f));
for(int i=; i<=; i++)
{
phi[i]=;
f[i]=;
}
phi[]=;
for(int i=; i<=; i++)
{
if(!phi[i])
{
for(ll j=i; j<=; j+=i)
{
if(!phi[j]) phi[j]=j;
phi[j]=phi[j]/i*(i-);
cnt[j][f[j]++]=i;//算是哈希吧,很精辟啊，这种写法要学习
}
}
phi[i]+=phi[i-];
}
}
ll gcd(ll A,ll B)
{
return B==?A:gcd(B,A%B);
}
void dfs(ll now,ll num,ll lcm,ll &coun,int key)
{
lcm=cnt[key][now]/gcd(cnt[key][now],lcm)*lcm;
if(num&)
{
coun+=b/lcm;
}
else
{
coun-=b/lcm;
}
for(ll i=now+; i<f[key]; i++)
dfs(i,num+,lcm,coun,key);
}
int main()
{
int T,K=;
init();
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d%d%d",&a,&b,&c,&d,&x);
if(x == || x > b || x > d)
{
printf("Case %d: 0\n",++K);
continue;
}
b/=x;
d/=x;
sum=;
if(b>d) swap(b,d);
sum+=phi[b];
for(int i=b+; i<=d; i++)
{
ll coun=;
for(int j=; j<f[i]; j++)
{
dfs(j,,cnt[i][j],coun,i);
}
sum+=(b-coun);
}
printf("Case %d: %I64d\n",++K,sum);
}
return ;
}
TLE的：（TLE了一中午 3000ms++)
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <math.h>
using namespace std;
typedef __int64 ll;
ll a,b,c,d,x,sum,top,cnt[],we;//********
int phi[],su[],prime[];
void init()
{
we=;
prime[we++]=;
su[]=su[]=;
su[]=;
for(int i=; i<; i++)
if(i%==) su[i]=;
else su[i]=;
double t=sqrt(*1.0);
for(ll i=; i<=t; i++)
{
if(su[i])
{
for(ll j=i*i; j<; j=j+i)
{
su[j]=;
}
}
}
for(ll i=; i<=; i++)
{
if(su[i]) prime[we++]=i;
}
memset(phi,,sizeof(phi));
phi[]=;
for(ll i=; i<=; i++)
{
if(!phi[i])
{
for(ll j=i; j<=; j+=i)
{
if(!phi[j]) phi[j]=j;
phi[j]=phi[j]/i*(i-);
}
}
}
}
ll gcd(ll A,ll B)
{
return B==?A:gcd(B,A%B);
}
void dfs(ll now,ll num,ll lcm,ll &coun)
{
lcm=cnt[now]/gcd(cnt[now],lcm)*lcm;
if(num&)
{
coun+=b/lcm;
//printf("hsum======%I64d\n",sum);
}
else
{
coun-=b/lcm;
}
for(ll i=now+; i<top; i++)
dfs(i,num+,lcm,coun);
}
void cal(ll key,ll &coun)
{
top=;
ll KK=;
for(ll i=prime[]; i<=key; i=prime[++KK])
{
if(key%i==)
{
cnt[top++]=i;
key/=i;
while(key%i==)
key/=i;
}
}
if(key!=)
{
cnt[top++]=key;
}
for(ll i=; i<top; i++)
{
dfs(i,,cnt[i],coun);
}
}
int main()
{
int T,K=;
init();
scanf("%d",&T);
while(T--)
{
scanf("%I64d%I64d%I64d%I64d%I64d",&a,&b,&c,&d,&x);
if(x == || x > b || x > d)
{
printf("Case %d: 0\n",++K);
continue;
} b/=x;
d/=x;
sum=;
if(b>d) swap(b,d);
//cout<<"b=="<<b<<" "<<"d=="<<d<<endl;
for(int i=; i<=b; i++)
{
sum+=phi[i];
}
//cout<<"sumsss=="<<sum<<endl;
for(ll i=b+; i<=d; i++)
{
if(su[i])
{
sum+=b;
continue;
}
ll coun=;
cal(i,coun);
sum+=(b-coun);
}
printf("Case %d: %I64d\n",++K,sum);
}
return ;
}