Description
FGD正在破解一段密码，他需要回答很多类似的问题：对于给定的整数a,b和d，有多少正整数对x,y，满足x<=a，y<=b，并且gcd(x,y)=d。作为FGD的同学，FGD希望得到你的帮助。
Input
第一行包含一个正整数n，表示一共有n组询问。（1<=n<= 50000）接下来n行，每行表示一个询问，每行三个
正整数，分别为a,b,d。（1<=d<=a,b<=50000）
Output
对于每组询问，输出到输出文件zap.out一个正整数，表示满足条件的整数对数。
Sample Input
2
4 5 2
6 4 3
Sample Output
3
2
容斥定理（莫比乌斯函数）。
代码：
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=5e4+10;
int prime[6100],tot,miu[N];bool v[N];
void get_prime()
{
miu[1]=1;
for(int i=2;i<N-5;i++)
{
if(!v[i])prime[++tot]=i,miu[i]=-1;
for(int j=1;j<=tot&&(ll)i*prime[j]<N-5;j++)
{
v[i*prime[j]]=1;
//因为原来的初始化，i*prime[j]比i多一个质因数，所以miu[i*prime[j]]应与miu[i]互为相反数。
//特殊地，当p^2|a时，a一定会被a/p包含，所以miu[a]=0;
if(i%prime[j]==0){miu[i*prime[j]]=0;break;}
miu[i*prime[j]]=-miu[i];
}
miu[i]+=miu[i-1];
}
}
#define g getchar()
void qr(int &x)
{
char c=g;x=0;
while(!('0'<=c&&c<='9'))c=g;
while('0'<=c&&c<='9')x=x*10+c-'0',c=g;
}
void write(ll x)
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
int main()
{
/*问题：给定a，b，d，求满足gcd(x,y)==d(x<=a,y<=b)的数对个数。
等价于有多少对(x,y),x<=a/d,y<=b/d,使得gcd(x,y)=1(因为x,y互质，x，y均乘以k,就是真实值。）
根据容斥原理,互质的数对的个数，等于a*b/d/d-(每一个质数的倍数）+（每两个质数的倍数）-……。
*/
get_prime();
int m;qr(m);
while(m--)
{
int a,b,d;qr(a);qr(b);qr(d);
a/=d;b/=d;
if(a>b)swap(a,b);
ll ans=0;
for(int i=1,r;i<=a;i=r+1)//之所以这样循环，是因为当i>a时，a中已经没有i的倍数了。
{
r=min(a/(a/i),b/(b/i));//处理i~r的数的倍数.
ans+=(ll)(miu[r]-miu[i-1])*(a/i)*(b/i);
}
write(ans);puts("");
}
return 0;
}