莫比乌斯反演习题：bzoj 2154 Crash的数字表格

题目描述

给定$n,m$，求$\sum_{i=1}^{n}\sum_{j=1}^{m}\text{lcm}(i,j)$

$n,m \le 10^7$

题解

$$
\begin{aligned}
n \le m \\
\sum_{i=1}^{n}\sum_{j=1}^{m}\text{lcm}(i,j)
&=\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{ij}{(i,j)} \\
&=\sum_{d=1}^{n}\frac{d^2}{d}\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}ij[(i,j)=1] \\
&=\sum_{d=1}^{n}d\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}ij[(i,j)=1] \\
&=\sum_{d=1}^{n}d\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}ij\sum_{d’ \mid (i,j)}\mu(d’) \\
&=\sum_{d=1}^{n}d\sum_{d’=1}^{\lfloor \frac{n}{d} \rfloor}\mu(d’)\sum_{i=1 \wedge d’ \mid i}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1 \wedge d’ \mid j}^{\lfloor \frac{m}{d} \rfloor}ij \\
&=\sum_{d=1}^{n}d\sum_{d’=1}^{\lfloor \frac{n}{d} \rfloor}\mu(d’)\sum_{i=1}^{\lfloor \frac{n}{dd’} \rfloor}id’\sum_{j=1}^{\lfloor \frac{m}{dd’} \rfloor}jd’ \\
&=\sum_{d=1}^{n}d\sum_{d’=1}^{\lfloor \frac{n}{d} \rfloor}\mu(d’)(d’)^2 \frac{(1+\lfloor \frac{n}{dd’} \rfloor)\lfloor \frac{n}{dd’} \rfloor}{2} \frac{(1+\lfloor \frac{m}{dd’} \rfloor)\lfloor \frac{m}{dd’} \rfloor}{2} \\
&=\sum_{T=1}^{n}\frac{(1+\lfloor \frac{n}{T} \rfloor)\lfloor \frac{n}{T} \rfloor}{2}\frac{(1+\lfloor \frac{m}{T} \rfloor)\lfloor \frac{m}{T} \rfloor}{2} \sum_{d \mid T}\frac{T}{d}\mu(d)d^2\\
&=\sum_{T=1}^{n}\frac{(1+\lfloor \frac{n}{T} \rfloor)\lfloor \frac{n}{T} \rfloor}{2}\frac{(1+\lfloor \frac{m}{T} \rfloor)\lfloor \frac{m}{T} \rfloor}{2} T\sum_{d \mid T}\mu(d)d\\
&=\sum_{T=1}^{n}\frac{(1+\lfloor \frac{n}{T} \rfloor)\lfloor \frac{n}{T} \rfloor}{2}\frac{(1+\lfloor \frac{m}{T} \rfloor)\lfloor \frac{m}{T} \rfloor}{2} Tf(T) \\
&=\sum_{T=1}^{n}\frac{(1+\lfloor \frac{n}{T} \rfloor)\lfloor \frac{n}{T} \rfloor}{2}\frac{(1+\lfloor \frac{m}{T} \rfloor)\lfloor \frac{m}{T} \rfloor}{2} g(T) \\
\end{aligned}
$$

之后考虑$g(T)=Tf(T)$怎么求，即求$f(T)=\sum_{d \mid T}\mu(d)d$

考虑线性筛，假设当前枚举到了$i$，且枚举到了素数$p_j$

若$i$是素数，则$f(i)=\sum_{d \mid i}\mu(i)i=\mu(1)1+\mu(i)i=1-i$

若$p_j \mid i$，则$f(ip_j)=\sum_{d \mid ip_j}\mu(d)d=\sum_{d\text{中没有}p_j}\mu(d)d+\sum_{d\text{中有}p_J}\mu(d)d=f(i)$

若$p_j\not \mid i$，则

$$
\begin{align}
f(ip_j)
&=\sum_{d \mid ip_j}\mu(d)d \\
&=\sum_{d\text{中没有}p_j}\mu(d)d+\sum_{d\text{中有}p_J}\mu(d)d \\
&=f(i)+\sum_{ap_j \mid ip_j}\mu(ap_j)ap_j \\
&=(1-p_j)f(i)
\end{align}
$$

代码

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int N = 1e7 + 10, mod = 20101009;

ll f[N], g[N];
int vis[N], p[N], tot, n, m;

int main() {
    scanf("%d%d", &n, &m); if(n > m) swap(n, m);
    f[1] = 1;
    for(int i = 2 ; i <= m ; ++ i) {
        if(!vis[i]) {
            p[++ tot] = i;
            f[i] = (1 - i) % mod;
        }
        for(int j = 1 ; j <= tot && (ll) i * p[j] <= m ; ++ j) {
            vis[i * p[j]] = 1;
            if(i % p[j] == 0) {
                f[i * p[j]] = f[i];
                break;
            } else {
                f[i * p[j]] = (1 - p[j]) * f[i] % mod;
            }
        }
    }
    for(int i = 1 ; i <= m ; ++ i) g[i] = (f[i] * i % mod + g[i - 1]) % mod;
    ll ans = 0;
    for(int i = 1, j ; i <= n ; i = j + 1) {
        j = min(n / (n / i), m / (m / i));
        ans += 
            (
            ((ll) (1 + n / i) * (n / i) / 2 % mod)
          * ((ll) (1 + m / i) * (m / i) / 2 % mod) % mod
          * ((g[j] - g[i - 1]) % mod)
          ) % mod;
        ans %= mod;
    }
    printf("%lld\n", (ans % mod + mod) % mod);
}