算法

(莫比乌斯函数、线性筛) $\mathcal{O}(n)$

首先发现题目可以转化为：

求有多少个数对 $(x, y)$ 满足 $x \in [1, \frac{n}{k}]$，$y \in [1, \frac{m}{k}]$，且 $\gcd(x, y) = 1$ 。

令 $n’ = \frac{n}{k}$，$m’ = \frac{m}{k}$

有序数对问题可以写成：

$$ \sum_{i=1}^{n’}\sum_{j=1}^{m’} [\gcd(i, j) = 1] $$

联系一个式子：

$$ [n=1] = \sum_{i \mid n} \mu(i) $$

问题可以写成：

$$ \sum_{i=1}^{n’}\sum_{j=1}^{m’} \sum_{d \mid \gcd(i, j)} \mu(d) $$

可以进一步写成：

$$ \sum_{i=1}^{n’}\sum_{j=1}^{m’}\sum_{d \mid i, \, d \mid j} \mu(d) $$

把 $d$ 移到最前面来

$$ \sum_d \mu(d) \sum_{i=1}^{\frac{n’}{d}}\sum_{j=1}^{\frac{m’}{d}} 1 $$

进一步等价于：

$$ \sum_{d}\mu(d) \lfloor\frac{n’}{d}\rfloor \lfloor\frac{m’}{d}\rfloor $$

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

// linear sieve
vector<bool> isp;
vector<int> ps, pf, mu;
void sieve(int mx) {
    isp.resize(mx+1);
    pf.resize(mx+1);
    mu.resize(mx+1);
    mu[1] = 1;
    rep(i, mx+1) pf[i] = i;
    for (int i = 2; i <= mx; ++i) {
        if (pf[i] == i) isp[i] = true, ps.push_back(i), mu[i] = -1;
        rep(j, ps.size()) {
            int x = ps[j]*i;
            if (x > mx) break;
            pf[x] = ps[j];
            if (i%ps[j] == 0) {
                mu[i*ps[j]] = 0;
                break;
            }
            mu[i*ps[j]] = -mu[i];
        }
    }
}

int main() {
    sieve(1e6);

    int n, m, k;
    cin >> n >> m >> k;
    n /= k; m /= k;

    if (n > m) swap(n, m);

    ll ans = 0;
    for (int d = 1; d <= n; ++d) {
        ans += (ll)mu[d]*(n/d)*(m/d);
    }

    cout << ans << '\n';

    return 0;
}