题目描述

给定$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}
$$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#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);
}