[NOI 2010] 能量采集

题目大意

给定 nnmm,求:

i=1nj=1m2×gcd(i,j)1\sum_{i = 1}^{n} \sum_{j = 1}^{m} 2 \times gcd(i, j) - 1

1n, m100,0001 \leqslant n, \ m \leqslant 100,000

题目链接

【NOI 2010】能量采集 - Luogu 1447

题解

莫比乌斯反演。

f(x)=i=1nj=1m[gcd(i,j)=x]f(x) = \sum_{i = 1}^{n} \sum_{j = 1}^{m} [gcd(i, j) = x]

题目即求

i=1min(n,m)i×f(i)\sum_{i = 1}^{min(n, m)} i \times f(i)

对于 f(x)f(x) 的计算,记

F(x)=i=1nj=1m[xgcd(i,j)]=nxmiF(x) = \sum_{i = 1}^{n} \sum_{j = 1}^{m} [x | gcd(i, j)] = \lfloor \frac{n}x \rfloor \lfloor \frac{m}i \rfloor

\begin{align} F(x) &= \sum_{x | d} \mu(\frac{d}x) f(d) \\ &= \sum_{i = 1}^{\lfloor \frac{n}x \rfloor} \mu(i) f(ix) \\ f(x) &= F(x) - \sum_{i = 2}^{\lfloor \frac{n}x \rfloor} \mu(i) f(ix) \\ \end{align}

由此计算即可。

另外,在 【HAOI 2011】problem b 中,我们得到了另一计算 f(x)f(x) 的式子,理论上用那个也能算,时间复杂度应该相同,均为 O(nn)O(n \sqrt{n})(经 VW 学长更正:为 O(nlogn)O(n\log n),调和数的增长是对数的),但本篇的式子编写代码时更简单。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstdio>
#include <algorithm>
const int MAXN = 100005;
long long f[MAXN];
int main() {
int n, m;
scanf("%d %d", &n, &m);
if (n > m) std::swap(n, m);
long long ans = 0;
for (int i = n; i; i--) {
f[i] = (long long) (n / i) * (m / i);
for (int j = 2; i * j <= n; j++) f[i] -= f[i * j];
ans += f[i] * ((i << 1) - 1);
}
printf("%lld\n", ans);
return 0;
}