不知道为什么下面的$Latex$不行，建议来蒟蒻的博客看看

传送门

思路

题目让我们求$x\leq a,y\leq b$有多少对$(x,y)$满足$\gcd(x,y)=d$
等价于求
有多少对$(x,y)$满足$x\leq x/d,y \leq b/d$，使得$\gcd(x,y)=1$
设$d(a,b,k)$表示有多少对$(x,y)$满足$x\leq a,y \leq b$且$k|gcd(a,b)$
$$d(a,b,k)=\left\lfloor\dfrac{a}{k}\right\rfloor*\left\lfloor\dfrac{b}{k}\right\rfloor$$
这式子是能用整除分块优化
设$f(a,b)$表示有多少对$(x,y)$满足$x\leq a,y \leq b$且$gcd(x,y)=1$
根据容斥原理得
$$f(a,b)=\mu(i)*d(a,b,i)$$
这里意思大概就是没有任何限制的二元组数量为$d(a,b,1)$，然后减去$gcd(x,y)$是$2,3,5……$的倍数的二元组数量，然后加回来$gcd(x,y)$既是$2$又是$3$的倍数的……

$code$

/*
@ author:pyyyyyy
-----思路------
-----debug-------
memset(miu,1,sizeof(miu))不是把miu全赋值成1,我傻了 
*/
#include<bits/stdc++.h>
using namespace std;
const int N=50041;
int T,a,b,d;
int miu[N],v[N];
void prime(int n)
{
    for(int i=2;i<=n;++i)
    {
        if(v[i]) continue;
        miu[i]=-1;
        for(int j=2*i;j<=n;j+=i)
        {
            v[j]=1;
            if((j/i)%i==0) miu[j]=0;
            else miu[j]*=-1;
        }
    }
}
int Zap(){
    a/=d,b/=d;
    int ans=0;
    if(a>b) swap(a,b);
    for(int l=1,r;l<=a;l=r+1)
    {
        r=min(a/(a/l),b/(b/l));
        ans+=(miu[r]-miu[l-1])*(a/l)*(b/l);
    }
    return ans;
}
int main()
{
    for(int i=1;i<N;++i) miu[i]=1;
    prime(N);
    for(int i=1;i<N;++i) miu[i]+=miu[i-1];
    cin>>T;
    while(T--)
    {
        cin>>a>>b>>d;
        cout<<Zap()<<'\n';  
    }   
    return 0;
}