[BZOJ 2005][NOI 2010] 能量采集

题目大意

给定 \(n\)\(m\),求: \[ \sum_{i = 1}^{n} \sum_{j = 1}^{m} 2 \times gcd(i, j) - 1 \] \(1 \leqslant n, \ m \leqslant 100,000\)

题目链接

BZOJ 2005

CodeVS 1937

题解

莫比乌斯反演。

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

题目即求

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

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

\[F(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} \] 由此计算即可。

另外,在 BZOJ 2301中,我们得到了另一计算 \(f(x)\) 的式子,理论上用那个也能算,时间复杂度应该相同,均为 \(O(n \sqrt{n})\)(经 VW 学长更正:为 \(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;
}