洛谷 - P2158 仪仗队

#题面

#题目描述

作为体育委员，C 君负责这次运动会仪仗队的训练。仪仗队是由学生组成的 $N \times N$ 的方阵，为了保证队伍在行进中整齐划一，C 君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐（如下图）。

现在，C 君希望你告诉他队伍整齐时能看到的学生人数。

#输入格式

一行，一个正整数 $N$。

#输出格式

输出一行一个数，即 C 君应看到的学生人数。

#输入输出样例

输入 #1

4

输出 #1

9

#数据范围与说明

对于 $100\%$ 的数据，$1 \le N \le 40000$。

#思路

设 C 君的坐标为原点建立一个平面直角坐标系。

容易发现相同的斜率只能有一个，否则会被挡住，可以推出当一个点的横坐标与纵坐标的最大公约数大于 1 时就会被遮挡。

所以问题就被转化成了找所有满足 $\gcd(x, y) = 1$ 的整数对，使用莫比乌斯反演即可解决。

推导过程：

设 $f(n)$ 为 $\gcd(x, y)$ 为 $n$ 的整数对个数， $F(n)$ 表示 $n | \gcd(x, y)$ 的整数对个数

可得 $F(n) = \sum\limits_{n|d} f(d)$ 。

反演得 $f(n) = \sum\limits_{n|d} \mu(\frac{d}{n}) F(d)$ 。

容易发现 $F(d) = {\lfloor\frac{N}{d}\rfloor}^{2}$ 。

整理得 $f(n) = \sum\limits_{n|d} \mu(\frac{d}{n}) {\lfloor\frac{n}{d}\rfloor}^{2}$ 。

最后求 $f(1)$ 即为答案。

最后还需要加上 $(0, 1)$ 和 $(1, 0)$ 两个点。

还需要特判当 $n = 1$ 时的情况，因为此时仪仗队内仅有 C 君一人。

#代码

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

#include <bits/stdc++.h>

using namespace std;

int n, p, ans, mu[40005], primes[40005];
bool vis[40005];

int main() {
    cin >> n;
    if (!--n) {
        cout << 0 << endl;
        exit(0);
    }
    mu[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            primes[++p] = i;
            mu[i] = -1;
        }
        for (int j = 1; i * primes[j] <= n; j++) {
            vis[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
            mu[i * primes[j]] = -mu[i];
        }
    }
    for (int i = 1; i <= n; i++) {
        ans += mu[i] * pow(n / i, 2);
    }
    cout << ans + 2 << endl;
    return 0;
}