「洛谷 P1390」公约数的和 - 莫比乌斯反演

发表于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

给定 \(n\)，求

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

其中 \(\gcd(i, j)\) 表示 \(i\) 和 \(j\) 的最大公约数。

数据范围：\(2 \leq n \leq 2 \times 10^6\)。

解题思路

问题转化

我们设函数 \(A(n) = \sum_{i = 1}^n \sum_{j = i + 1}^n \gcd(i, j)\)，很显然 \(A(n)\) 即为答案。

对于 \(A(n)\) 不好求 我直接硬刚了好久算出来还是错的 QWQ，于是我们可以简化一下。我们可以设 \(B(n) = \sum_{i = 1}^n \sum_{j = 1}^n \gcd(i, j)\)。根据容斥原理，可得下列关系：

\[ \begin{align*} A(n) &= \frac{B(n) - \sum_{i = 1}^n i}{2} \\ &= \frac{ B(n) - \frac{n^2 - n}{2} }{2} \end{align*} \]

于是我们问题转为求 \(B(n)\) 的值。

莫比乌斯反演

我们设函数 \(f(x) = \sum_{i = 1}^n \sum_{j = 1}^n [\gcd(i, j) = 1]\)，很显然 \(B(n) = \sum_{i = 1}^n{i f(i)}\)。

接着我们设函数 \(F(d) = \sum_{d | x}{f(x)}\)，于是可做下列代数变化：

\[ \begin{align*} F(d) &= \sum_{d | x}{f(x)} \\ &= \sum_{d | x} \sum_{i = 1}^n \sum_{j = 1}^n [\gcd(i, j) = x] \\ &= \sum_{t = 1}^{\lfloor \frac{n}{d} \rfloor} \sum_{i = 1}^n \sum_{j = 1}^n [\gcd(i, j) = td] \\ &= \sum_{i = 1}^n \sum_{j = 1}^n [d | \gcd(i, j)] \\ &= \sum_{i = 1}^n \sum_{j = 1}^n [d | i][d | j] \\ &= {\lfloor \frac{n}{d} \rfloor}^2 \end{align*} \]

于是我们可以进行莫比乌斯反演：

\[ \begin{align*} f(x) &= \sum_{x | d}{\mu(\frac{d}{x}) F(d)} \\ &= \sum_{x | d}{\mu(\frac{d}{x}) {\lfloor \frac{n}{d} \rfloor}^2} \\ &= \sum_{t = 1}^{\lfloor \frac{n}{x} \rfloor}{\mu(t) {\lfloor \frac{n}{xt} \rfloor}^2} \end{align*} \]

故我们可得：

\[ \begin{align*} B(n) &= \sum_{i = 1}^n{i \sum_{t = 1}^{\lfloor \frac{n}{x} \rfloor}{\mu(t) {\lfloor \frac{n}{xt} \rfloor}^2} } \\ &= \sum_{i = 1}^n{ \sum_{t = 1}^{\lfloor \frac{n}{x} \rfloor}{i \mu(t) {\lfloor \frac{n}{xt} \rfloor}^2} } \\ &= \sum_{d = 1}^n \sum_{x | d}{x \mu(\frac{d}{x}) {\lfloor \frac{n}{d} \rfloor}^2} \\ &= \sum_{d = 1}^n{ {\lfloor \frac{n}{d} \rfloor}^2 \sum_{x | d}{x \mu(\frac{d}{x})} } \end{align*} \]

欧拉函数处理

为了处理 \(B(n)\)，我们可以引出一条引理：

\[ \sum_{x | d}{x \mu(\frac{d}{x})} = \varphi(d) \]

证明：由欧拉函数的性质可得 \(\sum_{d | x} \varphi(d) = x\)，于是我们可由莫比乌斯反演得：\(\varphi(x) = \sum_{d | x}{ \mu(d) \frac{n}{x} }\)，该式与原式等价，得证。

于是带入 \(B(n)\)，可得：

\[ B(n) = \sum_{d = 1}^n{ {\lfloor \frac{n}{d} \rfloor}^2 \varphi(d) } \]

带入 \(A(n)\)，可得出答案：

\[ A(n) = \frac{ \sum_{d = 1}^n{ {\lfloor \frac{n}{d} \rfloor}^2 \varphi(d) } - \frac{n^2 - n}{2} }{2} \]

于是我们仅需线性筛出 \(\varphi(x)\)，接着直接计算即可。

代码演示

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
#include <cstdio>
#include <cstring>

const int MAXN = 2e6;

int v[MAXN + 1], prime[MAXN + 1], phi[MAXN + 1], m;

void euler(int n) {
    memset(v, 0, sizeof(v));
    phi[1] = 1, m = 0;
    for (int i = 2; i <= n; i++) {
        if (v[i] == 0) {
            v[i] = i;
            prime[++m] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= m; j++) {
            if (prime[j] > v[i] || prime[j] > n / i) break;
            v[i * prime[j]] = prime[j];
            phi[i * prime[j]] = phi[i] * (i % prime[j] ? prime[j] - 1 : prime[j]);
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);

    euler(n);

    long long ans = 0;
    for (int i = 1; i <= n; i++) ans += 1ll * (n / i) * (n / i) * phi[i];
    ans = (ans - (1ll * n * n + n) / 2) / 2;

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

    return 0;
}