题意简述：对于给定的整数a,b和d，有多少正整数对x,y，满足x<=a，y<=b，并且gcd(x,y)=d。

Solution

很显然这是一个莫比乌斯反演题。

\[ ans=\sum_{i=1}^{a}\sum_{j=1}^{b}[gcd(i,j)=d] \]

然后我们设

\[ f(d)=ans=\sum_{i=1}^{a}\sum_{j=1}^{b}[gcd(i,j)=d]\\ g(x)=\sum_{x|d}f(d) \]

有

\[ f(x)=\sum_{x|d}\mu(\frac{d}{x})g(d) \]

因为

\[ g(x)=\sum_{i=1}^{a}\sum_{i=1}^{b}[x|gcd(i,j)]=\sum_{i=1}^{a/x}\sum_{i=1}^{b/x}[1|gcd(i,j)]=\frac{a}{x}\frac{b}{x} \]

然后可以\(f(x)\)可以变成这样

\[ f(x)=\sum_{x|d}\mu(\frac{d}{x})\frac{a}{d}\frac{b}{d} \]

我们设\(t=\frac{d}{x}\),\(f(x)\)就成了这样

\[ f(x)=\sum_{t=1}^{min(a,b)}\mu(t)\frac{a}{dx}\frac{b}{dx} \]

此时\(f(x)\)已经可以\(O(n)\)计算了，但是由于多组询问，还需要采取数论分块的方式将时间复杂度优化到\(O(\sqrt{n})\)

代码：

#include
    
     #include
     
      #include
      
       using namespace std;void read(int &x) {    char ch; bool ok;    for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;    for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;}#define rg registerconst int maxn=5e4;long long ans;int n,m,d,mu[maxn],prime[maxn],T,tot;bool vis[maxn];void prepare(){    mu[1]=1;    for(rg int i=2;i<=maxn;i++)    {        if(!vis[i])prime[++tot]=i,mu[i]=-1;        for(rg int j=1;j<=tot&&prime[j]*i<=maxn;j++)        {            vis[i*prime[j]]=1;            if(i%prime[j])mu[i*prime[j]]=-mu[i];            else {mu[i*prime[j]]=0;break;}        }    }    for(rg int i=1;i<=maxn;i++)mu[i]+=mu[i-1];}int main(){    read(T);prepare();    while(T--)    {        read(n),read(m),read(d);if(n>m)swap(n,m);        ans=0;        for(rg int i=1,j;i<=n;i=j+1)        {            j=min(n/(n/i),m/(m/i));            long long t=1ll*(n/i/d)*(m/i/d);            ans+=t*(mu[j]-mu[i-1]);        }        printf("%lld\n",ans);    }}