人生第一道莫比乌斯反演题，写写题解吧

如果markdown有锅请移步至这里

定义

题目让我们求

$$\sum_{a=1}^{A}\sum_{b=1}^{B}[\gcd(a\in A,b\in B)=d]$$

显然，我们可以采用莫比乌斯反演的方式来求出这个式子

我们可以记

$$f(x)=\begin{cases}1\ \ \ (x=d)\\\\ 0\ \ \ (x\ne d)\end{cases}$$

也就是说，我们需要找到$g$且$f=g\times 1$，即

$$f(x)=\sum_{k\mid x}g(x)$$

又因为1的逆为$\mu$，所以我们可以得出以下结论

$$\begin{cases}g=f\times\mu\\ \\ \displaystyle \displaystyle g(x)=\sum_{k\mid x}\mu(\frac{x}{k})[k=d]\\ \displaystyle g(x)=\mu(\frac{x}{d})[d\mid x]\end{cases}$$

也就是说，我们可以通过化简得到以下的式子

$$\sum_{k=1}^{\min(A,B)}g(k)\lfloor \frac{A}{k}\rfloor\times \lfloor\frac{B}{k}\rfloor$$

然后我们就可以通过数论分块的方法求出这个式子了

至于$g$，我们可以用线性筛把$\mu$筛出来，再前缀和即可

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
#define int long long

using namespace std;

namespace MAIN {
    const int SIZE = 1000000 + 5;
    int a, b, d, tot, ans, primes[SIZE];
    int Mobius[SIZE], tag[SIZE];

    inline void MAIN() {
        scanf("%lld %lld %lld", &a, &b, &d);
        Mobius[1] = 1;
        for (int i = 2; i <= max(a, b); ++i) { // 线性筛
            if (!tag[i]) primes[++tot] = i, Mobius[i] = -1;
            for (int j = 1; j <= tot; ++j) {
                if (i * primes[j] > max(a, b)) break;
                tag[i * primes[j]] = 1;
                if (!(i % primes[j])) {
                    Mobius[i * primes[j]] = 0;
                    break;
                }
                Mobius[i * primes[j]] = -Mobius[i];
            }
        }
        for (int i = d; i <= min(a, b); i += d) ans += Mobius[i / d] * (a / i) * (b / i);
        printf("%lld\n", ans);
    }
} // namespace MAIN

signed main() {
    MAIN::MAIN();
}