题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1101

题意：略。

思路：化柿子：
\sum_{i=1}^{a}\sum_{j=1}^{b}[gcd(i,j)==d]
=\sum_{i=1}^{\lfloor a/d\rfloor}\sum_{j=1}^{\lfloor b/d\rfloor}[gcd(i,j)==1]
=\sum_{i=1}^{\lfloor a/d\rfloor}\sum_{j=1}^{\lfloor b/d\rfloor}\sum_{d|gcd(i,j)}\mu(d)
枚举d，d|gcd(i,j)满足条件的对数易知是\lfloor i/d\rfloor \lfloor j/d\rfloor，所以:
=\sum_{d=1}^{min(\lfloor a/d\rfloor,\lfloor b/d\rfloor)}\mu(d)\lfloor \lfloor a/d\rfloor/d\rfloor\lfloor \lfloor b/d\rfloor/d\rfloor
然后就预处理莫比乌斯函数前缀和分块求和即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=50000+10;
int _,a,b,d,i,j,last,ans,mu[N],primes[N],sum[N];
void init(){
    for (sum[1]=mu[1]=1,i=2;i<=50000;i++){
        if (!primes[i]) primes[++primes[0]]=i,mu[i]=-1;
        for (j=1;j<=primes[0]&&i*primes[j]<=50000;j++){
            primes[i*primes[j]]=1;
            if (i%primes[j]==0){
                mu[i*primes[j]]=0;
                break;
            }
            else mu[i*primes[j]]=-mu[i];
        }
        sum[i]=sum[i-1]+mu[i];
    }
}
int main(){
    init();
    for (read(_);_--;){
        read(a),read(b),read(d);
        if (a>b) swap(a,b);
        a/=d,b/=d;
        for (ans=0,i=1;i<=a;i=last+1){
            last=min(a/(a/i),b/(b/i));
            ans+=(sum[last]-sum[i-1])*(a/i)*(b/i);
        }
        printf("%d\n",ans);
    }
    return 0;
}