题目链接。
我们定义 \(n\) 的莫比乌斯函数为 \(\mu_n\)。
我们将 \(n\) 分解质因式后为 \(n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}\) 则 \(\mu_n= \begin{cases}0\text{ 当 } \alpha_i > 1 \text{ 时}\\ 1\text{ 当 } k\text{ 为偶数时}\\ -1\text{ 当 } k\text{ 为奇数时} \end{cases}\)
\(\gcd(x, y)=d\)，就等价于 \(\gcd(\frac{x}{d}, \frac{y}{d})=1\)。
即为找到 \(x^{'}, y^{'}\) 满足 \(x^{'}\le\left\lfloor\frac{a}{d}\right\rfloor, y^{'}\le \left\lfloor\frac{b}{d}\right\rfloor\) 和 \(\gcd(x^{'}, y^{'}) = 1\)。
假如不考虑条件 \(2\)，我们令 \(a^{'}=\left\lfloor\frac{a}{d}\right\rfloor, b^{'}=\left\lfloor\frac{b}{d}\right\rfloor\)。则答案为 \(a^{'}b^{'}\)。
想必大家都知道容斥原理把，即答案为
\[a^{'}b^{'}-S_2-S_3-S_5-\cdots\\ +S_6+S_{10}+S_{15}+\cdots\\ -S_{30}-\cdots\\ \]其中 \(S_i\) 表示 \(\left\lfloor\frac{\min\{a^{'}, b^{'}\}}{i}\right\rfloor\) 即 \([1, \min\{a^{'}, b^{'}\}]\) 中所有 \(i\) 的倍数的个数。
然后根据上面 \(\mu\) 的定义可得答案为 \(a^{'}b^{'}+\sum\limits_{i=2}^{\min\{a^{'}, b^{'}\}}\left\lfloor\frac{a}{i}\right\rfloor\left\lfloor\frac{b}{i}\right\rfloor\mu_i\)。
然后我们可以从 \(\left\lfloor\frac{a}{i}\right\rfloor\left\lfloor\frac{b}{i}\right\rfloor\) 入手，我们发现必定可以分成若干个极大段，使得段内值相等。
我们考虑对于一个分数 \(\frac{a}{b}\)，找到一个最大的整数 \(x\)，满足 \(\left\lfloor\frac{a}{b}\right\rfloor=\left\lfloor\frac{a}{x}\right\rfloor\)。
则 \(x = \left\lfloor\frac{a}{\left\lfloor\frac{a}{b}\right\rfloor}\right\rfloor\)。
如果满足以上条件即满足 \(\left\lfloor\frac{a}{b}\right\rfloor=\left\lfloor\frac{a}{x}\right\rfloor\) 和 \(\left\lfloor\frac{a}{b}\right\rfloor > \left\lfloor\frac{a}{x+1}\right\rfloor\)。
证明条件 \(1\)。
\[x=\left\lfloor\frac{a}{\left\lfloor\frac{a}{b}\right\rfloor}\right\rfloor\ge \left\lfloor\frac{a}{\frac{a}{b}}\right\rfloor=b\\ x\ge b\\ \left\lfloor\frac{a}{b}\right\rfloor\ge\left\lfloor\frac{a}{x}\right\rfloor\\ \left\lfloor\frac{a}{x}\right\rfloor=\left\lfloor\frac{a}{\left\lfloor\frac{a}{{\left\lfloor\frac{a}{b}\right\rfloor}}\right\rfloor}\right\rfloor\ge\left\lfloor\frac{a}{\frac{a}{\left\lfloor\frac{a}{b}\right\rfloor}}\right\rfloor=\left\lfloor\frac{a}{b}\right\rfloor\\ \left\lfloor\frac{a}{b}\right\rfloor=\left\lfloor\frac{a}{x}\right\rfloor \]证明条件 \(2\)。
设 \(a = kb + r\)，其中 \(0\le r<x\)。
\[\left\lfloor\frac{a}{b}\right\rfloor=k>\left\lfloor\frac{a}{x+1}\right\rfloor=\left\lfloor\frac{a}{\left\lfloor\frac{a}{{\left\lfloor\frac{a}{b}\right\rfloor}}\right\rfloor+1}\right\rfloor=\left\lfloor\frac{a}{\left\lfloor\frac{a}{k}\right\rfloor+1}\right\rfloor\\ k>\left\lfloor\frac{a}{\left\lfloor\frac{a}{k}\right\rfloor+1}\right\rfloor\\ k>\frac{a}{\left\lfloor\frac{a}{k}\right\rfloor+1}\\ k(\left\lfloor\frac{a}{k}\right\rfloor+1)>a \]在设 \(a=pk+q\)，其中 \(0\le q<k\)。
\[k(\left\lfloor\frac{a}{k}\right\rfloor+1)>a\\ k(p+1)>pk+q\\ kp+k>pk+q\\ k>q\\ \]从上面 \(0\le q < k\) 可知，\(k > q\)。
定理：将这些数分段段数必定是 \(\le \mathcal O(\sqrt{n})\) 的。
然后我们就可以每次跳到 \(\left\lfloor\frac{a}{i}\right\rfloor\left\lfloor\frac{b}{i}\right\rfloor\) 的末尾，再求出 \(\mu\) 的前缀和，然后根据分配律来求出上面的值。
\(\mathcal Code\)
#include <bits/stdc++.h>
#define x first
#define y second
#define IOS ios::sync_with_stdio(false)
#define cit cin.tie(0)
#define cot cout.tie(0)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 50010, M = 100010, MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LLINF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;
int primes[N], cnt;
bool st[N];
int mob[N], sum[N];
void solve();
void get_primes(int n)
{
mob[1] = 1;
for (int i = 2; i <= n; i ++ )
{
if (!st[i])
{
primes[cnt ++ ] = i;
mob[i] = -1;
}
for (int j = 0; primes[j] <= n / i; j ++ )
{
int t = primes[j] * i;
st[t] = true;
if (i % primes[j] == 0) break;
mob[t] = mob[i] * -1;
}
}
for (int i = 1; i <= n; i ++ ) sum[i] = sum[i - 1] + mob[i];
}
int main()
{
IOS;
cit, cot;
get_primes(N - 1);
int T = 1;
cin >> T;
while (T -- ) solve();
return 0;
}
void solve()
{
int a, b, d;
cin >> a >> b >> d;
a /= d, b /= d;
LL res = 0;
for (int l = 1, r; l <= min(a, b); l = r + 1)
{
r = min(a / (a / l), b / (b / l));
res += (sum[r] - (LL)sum[l - 1]) * (a / l) * (b / l);
}
cout << res << endl;
}