前置知识：莫比乌斯函数性质一（不会请点）
进入正题：
题目大意：
(T)组数据，每组给出(a),(b),(d)
求
[sum_{i=1}^a sum_{j=1}^b [gcd(i,j)=d]
]
解析
这题并不难
先变化一波
[sum_{i=1}^a sum_{j=1}^b [gcd(i,j)=d] = sum_{i=1}^a sum_{j=1}^b [gcd(frac{i}{d},frac{j}{d})=1]
]
现在我们知道 (i=i'*d) , (j=j'*d) 。
不妨，枚举 (i') 和 (j') ，则 (i') 最大为 (lfloor frac{a}{d}
floor) , (j') 最大为 (lfloor frac{b}{d}
floor) .
上式
[=sum_{i=1}^{lfloor frac{a}{d}
floor} sum_{j=1}^{lfloor frac{b}{d}
floor} [gcd(i,j)=1]
]
带入性质一
[egin{aligned}
&=sum_{i=1}^{lfloor frac{a}{d}
floor} sum_{j=1}^{lfloor frac{b}{d}
floor} sum_{k|gcd(i,j)} mu(k) \
&=sum_{k=1}^{min(lfloor frac{a}{d}
floor,lfloor frac{b}{d}
floor)} mu(k) lfloor frac{lfloor frac{a}{d}
floor}{k}
floor lfloor frac{lfloor frac{b}{d}
floor}{k}
floor \
end{aligned}
]
这样还是过不了，还要用数论分块，才能过。
时间复杂度(O(sqrt{lfloor frac{a}{d}
floor} + sqrt {lfloor frac{b}{d}
floor}))
代码：
#include<cstdio>
#include<iostream>
using namespace std;
int mo[60005],vis[60005],p[60005],tot=0;
void init()
{
mo[1]=1;
for (int i=2;i<=50005;i++)
{
if (!vis[i]) p[++tot]=i,mo[i]=-1;
for (int j=1;j<=tot&&p[j]*i<=50005;j++)
{
vis[p[j]*i]=1;
if (i%p[j]==0) break;
mo[p[j]*i]=-mo[i];
}
}
for (int i=1;i<=50005;i++) mo[i]+=mo[i-1];
}
int main()
{
init();
int t;
scanf("%d",&t);
while (t--)
{
int a,b,d,ans=0;
scanf("%d%d%d",&a,&b,&d);
a=a/d,b=b/d;
for (int l=1,r;l<=min(a,b);l=r+1)
{
r=min(a/(a/l),b/(b/l));
ans+=(a/l)*(b/l)*(mo[r]-mo[l-1]);
}
printf("%d
",ans);
}
}