主要思路

这道题是一道很好的题，包含了数论里面的很多技巧。

首先，这是一道多组询问的题，询问数量非常的大，遂放弃使用欧拉函数来求。考虑可以使用莫比乌斯函数的性质来搞，开始从这方面分析。

复习一下莫比乌斯函数的定义：

\[ \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;
}