$$ \sum_{i = 1}^n\sum_{j = 1}^m[\gcd(i, j) = d] $$
$$ \sum_{i = 1}^{n / d}\sum_{j = 1}^{m / d} [\gcd(i, j) = 1] $$
$$ \sum_{t = 1}^{n / d}\mu(t)\sum_{i = 1}^{n / d / t}\sum_{j = 1}^{m / d / t} $$
很基础很简单的莫比乌斯反演。
#include <bits/stdc++.h>
#define long long
const int N = 1e6;
bool st[N];
int prime[N], mu[N], cnt, smu[N];
std::unordered_map<int, int> Su;
int MAXN = 5e6;
inline void init()
{
mu[1] = 1;
for (int i = 2; i <= MAXN; i++)
{
if (!st[i])
{
prime[++cnt] = i;
mu[i] = -1;
}
for (int j = 1; prime[j] * i <= MAXN; j++)
{
st[prime[j] * i] = true;
if (i % prime[j] == 0)
break;
mu[prime[j] * i] = -mu[i];
}
}
for (int i = 1; i <= MAXN; i++)
smu[i] = smu[i - 1] + mu[i];
}
inline int g(int k, int x) { return k / (k / x); }
inline int s_mu(int n)
{
if (n < MAXN) return smu[n];
if (Su.count(n)) return Su[n];
int ans = 1;
for (int l = 2, r; l <= n; l = r + 1)
{
r = g(n, l);
ans -= (r - l + 1) * s_mu(n / l);
}
Su[n] = ans;
return ans;
}
int n, m, d;
auto main() -> signed
{
MAXN = 100000;
init();
int T; std::cin >> T;
while (T -- ) {
std::cin >> n >> m >> d;
int k = std::min(n, m);
int ans = 0;
for (int l = 1, r; l <= k; l = r + 1) {
r = std::min(g(n, l), g(m, l));
ans += (smu[r] - smu[l - 1]) * (n / d / l) * (m / d / l);
}
std::cout << ans << std::endl;
}
return 0;
}
写的好好看呀
我那个s_mu是杜教筛,本题可以不用的