Skip to content

洛谷 - P2158 仪仗队

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

本题有以下几种解法:

题面

题目描述

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

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

输入格式

一行,一个正整数 NN

输出格式

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

输入输出样例

输入 #1

4

输出 #1

9

数据范围与说明

对于 100%100 \% 的数据,1N400001 \le N \le 40000

思路

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

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

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

推导过程:

f(n)f(n)gcd(x,y)\gcd(x, y)nn 的整数对个数, F(n)F(n) 表示 ngcd(x,y)n | \gcd(x, y) 的整数对个数

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

反演得 f(n)=ndμ(dn)F(d)f(n) = \sum\limits_{n|d} \mu(\frac{d}{n}) F(d)

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

整理得 f(n)=ndμ(dn)nd2f(n) = \sum\limits_{n|d} \mu(\frac{d}{n}) {\lfloor\frac{n}{d}\rfloor}^{2}

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

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

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

代码

#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;
}