主要思路
这道题是一道很好的题，包含了数论里面的很多技巧。
首先，这是一道多组询问的题，询问数量非常的大，遂放弃使用欧拉函数来求。考虑可以使用莫比乌斯函数的性质来搞，开始从这方面分析。
复习一下莫比乌斯函数的定义：
\[ \mu(x) = \begin{cases} 0, 在x中存在指数大于一的质因子 \\ 1, 在x中质因子指数都为1且质因子个数为偶数 \\ -1, 在x中质因子质数都为1且质因子个数为奇数 \end{cases} \]
我们观察一下答案式子：\(\sum_{i,j} [gcd(x,y)=d]\)。我们先把\(gcd\)部分进行变换：
\[gcd(\frac{x}{d}, \frac{y}{d}) = 1\]
显然，这样的对数为\( \lfloor \frac{x}{d} \rfloor*\lfloor \frac{y}{d} \rfloor \)。我们考虑容斥：因为如果暴力累加的话，会多出很多不该存在的部分，比如说又是2的倍数又是3的倍数的部分。
所以最后答案式为：
\[\sum_{i=1}^{min\{a,b\}} \mu(i)*\lfloor \frac{x}{i} \rfloor*\lfloor \frac{y}{i} \rfloor \]
这时有个技巧，我们可以证明在整数段\([x, min\{ \lfloor \frac{a}{\lfloor \frac{a}{x} \rfloor} \rfloor, \lfloor \frac{b}{\lfloor \frac{b}{x} \rfloor} \rfloor \} ]\)上，\(\lfloor \frac{x}{i} \rfloor*\lfloor \frac{y}{i} \rfloor\)的结果是一样的，直接前缀和与之相乘即可。最后这样的段最坏情况为\(O(\sqrt{a}+\sqrt{b})\)，所以时间复杂度比较低。
代码
// BZ1101.cpp
#include <bits/stdc++.h>
#define ll int
using namespace std;
const int MAX_N = 5e4 + 200;
ll mobi[MAX_N], sum[MAX_N], n;
bool vis[MAX_N];
int main()
{
for (int i = 1; i < MAX_N; i++)
mobi[i] = 1;
for (int i = 2; i < MAX_N; i++)
{
if (vis[i])
continue;
mobi[i] = -1;
for (int j = 2; i * j < MAX_N; j++)
{
vis[i * j] = true;
if (j % i == 0)
mobi[i * j] = 0;
else
mobi[i * j] *= -1;
}
}
for (int i = 1; i < MAX_N; i++)
sum[i] = sum[i - 1] + mobi[i];
scanf("%d", &n);
while (n--)
{
int a, b, k, gx;
scanf("%d%d%d", &a, &b, &k);
a /= k, b /= k;
int ans = 0;
for (int i = 1; i <= min(a, b); i = gx + 1)
{
gx = min(a / (a / i), b / (b / i));
ans += (sum[gx] - sum[i - 1]) * (a / i) * (b / i);
}
printf("%d\n", ans);
}
return 0;
}