题面
题解
$$ \sum_{i=1}^a\sum_{j=1}^b[gcd(i,\;j)=d] \\ =\sum_{i=1}^{\left\lfloor\frac ad\right\rfloor}\sum_{j=1}^{\left\lfloor\frac bd\right\rfloor}[gcd(i,\;j)=1] \\ =\sum_{i=1}^p\mu(i)\lfloor\frac a{id}\rfloor\lfloor\frac b{id}\rfloor $$
筛一下$\mu$即可
代码
#include<bits/stdc++.h>
#define RG register
#define clear(x, y) memset(x, y, sizeof(x));
using namespace std;inline int read()
{
int data=0, w=1;
char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') w=-1, ch=getchar();
while(ch>='0'&&ch<='9') data=(data<<3)+(data<<1)+(ch^48), ch=getchar();
return data*w;
}const int maxn(100010);
int mu[maxn], prime[maxn], cnt, sum[maxn], n=100000, T, a, b, d;
bool not_prime[maxn];inline void getMu()
{
not_prime[1]=true; mu[1]=1;
for(RG int i=2;i<=n;i++)
{
if(!not_prime[i]) prime[++cnt]=i, mu[i]=-1;
for(RG int j=1;j<=cnt && i*prime[j] <= n;j++)
{
not_prime[i*prime[j]]=true;
if(i%prime[j]) mu[i*prime[j]]=-mu[i];
else { mu[i*prime[j]]=0; break; }
}
}
for(RG int i=1;i<=n;i++) sum[i]=sum[i-1]+mu[i];
}inline long long solve(int a, int b, int d)
{
a/=d; b/=d;
if(a > b) swap(a, b);
long long ans=0;
RG int i=1, j, k, l;
while(i<=a)
{
k=a/i; l=b/i;
j=min(a/k, b/l);
ans+=1ll*(sum[j]-sum[i-1])*k*l;
i=j+1;
}
return ans;
}int main()
{
getMu();
T=read();
while(T--) a=read(), b=read(), d=read(), printf("%lld\n", solve(a, b, d));
return 0;
}
