「Bzoj 3994」「SDOI2015」约数个数和 (莫比乌斯反演)

BZOJ 3994
题意：设$d(x)$为$x$的约数个数，给定$n,m$, 求
$$
\sum_{i=1}^n \sum_{j=1}^m d(ij)
$$

首先知道结论
$$
d(ij)=\sum_{a|i} \sum_{b|j} [\gcd(a,b)=1]
$$
具体可以通过展开唯一分解式子，根据 $gcd$ 性质，然后得出两个式子等价。
然后原答案可以化为
$$
\sum_{i=1}^n \sum_{j=1}^m \sum_{a|i} \sum_{b|j} [\gcd(a, b)=1]
$$
将$a,b$放到前面，并且改成$i,j$
$$
\sum_{i=1}^n \sum_{j=1}^m \lfloor \frac ni \rfloor \lfloor \frac mj \rfloor [\gcd(i, j)=1]
$$
设
$$
f(k)=\sum_{i=1}^n \sum_{j=1}^m \lfloor \frac ni \rfloor \lfloor \frac mj \rfloor [\gcd(i, j)=k] \\
g(k) = \sum_{i=1}^{\lfloor \frac nk \rfloor}f(ki) \\
$$
则
$$
g(k) =\sum_{i=1}^n \sum_{j=1}^m \lfloor \frac ni \rfloor \lfloor \frac mj \rfloor [k|\gcd(i, j)]
$$
将$k$提出来
$$
g(k) =\sum_{i=1}^{\lfloor \frac nk \rfloor} \sum_{j=1}^{\lfloor \frac mk \rfloor} \lfloor \frac n{ik} \rfloor \lfloor \frac m{jk} \rfloor
$$
由反演，得
$$
f(1)=\sum_{d=1}^n \mu(d) \sum_{i=1}^{\lfloor \frac nd \rfloor} \sum_{j=1}^{\lfloor \frac md \rfloor} \lfloor \frac n{di} \rfloor \lfloor \frac m{dj} \rfloor
$$
设$g(n)=\sum_\limits{i=1}^{n} \lfloor \frac ni \rfloor$，那么
$$
f(1)=\sum_{d=1}^n \mu(d) g(\lfloor \frac nd \rfloor) g(\lfloor \frac md \rfloor)
$$
预处理$g(n), \mu(n)$的前缀和，即可整除分块得到$O(T\sqrt n)$的复杂度

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

LL T;

namespace flyinthesky {

    const LL MAXN = 50000 + 5;

    LL n, m;
    LL mu[MAXN], vis[MAXN], pri[MAXN], tot;
    LL g[MAXN];

    void init() {
        tot = 0, ms(vis, 0), ms(mu, 0), ms(g, 0);
        mu[1] = 1;
        for (LL i = 2; i <= 50000; ++i) {
            if (!vis[i]) pri[++tot] = i, mu[i] = -1;
            for (LL j = 1; j <= tot && i * pri[j] <= 50000; ++j) {
                vis[pri[j] * i] = 1;
                if (i % pri[j] == 0) {
                    mu[i * pri[j]] = 0;
                    break;
                } else mu[i * pri[j]] = mu[i] * mu[pri[j]];
            }
        }
        for (LL i = 2; i <= 50000; ++i) mu[i] += mu[i - 1];
        for (LL i = 1; i <= 50000; ++i) {
            LL ans = 0, l = 1;
            while (l <= i) {
                LL r = i / (i / l);
                ans += (i / l) * (r - l + 1);
                l = r + 1;
            }
            g[i] = ans;
        }
    }

    void clean() {
    }
    int solve() {

        clean();
        scanf("%lld%lld", &n, &m);
        if (n > m) swap(n, m);

        LL ans = 0, l = 1;
        while (l <= n) {
            LL r = min(n / (n / l), m / (m / l));
            ans += (mu[r] - mu[l - 1]) * g[n / l] * g[m / l];
            l = r + 1;
        }
        /*for (LL i = 1; i <= m; ++i) {
            ans += (mu[i] - mu[i - 1]) * g[n / i] * g[m / i];
        }*/

        printf("%lld\n", ans);

        return 0;
    }
}
int main() {
    flyinthesky::init();
    scanf("%lld", &T);
    while (T--) flyinthesky::solve();
    return 0;
}