题解 | #[SDOI2008]仪仗队#

题目链接

[SDOI2008]仪仗队

题目描述

在一个 $N \times N$ 的学生方阵中，观察者站在左后方（坐标原点 $(0,0)$ ）。方阵的学生坐标为 $(x,y)$ ，其中 $1 \le x, y \le N$ 。

一个位于点 $(x,y)$ 的学生能被看到，当且仅当连接原点 $(0,0)$ 和点 $(x,y)$ 的线段上没有其他学生。你需要计算总共能看到多少名学生。

输入:

输入一行，包含一个整数 $N$ 。

输出:

输出一行，表示能看到的学生总数。

注意：根据题目样例（ $N=4$ ，输出 $9$ ），我们可以推断出实际的方阵是从 $(0,0)$ 到 $(N-1, N-1)$ 的区域，观察者位于 $(0,0)$ ，并且不计自身。因此，我们需要统计坐标 $(x,y)$ 在 $0 \le x, y \le N-1$ 范围内（ $x, y$ 不同时为 $0$ ）的可见点。

解题思路

这道题本质上是一个经典的数论问题，与欧拉函数紧密相关。

1. 可见性条件

一个位于点 $(x,y)$ 的学生能被观察者（位于 $(0,0)$ ）看到，意味着线段 $(0,0)-(x,y)$ 中间没有其他整数坐标点。如果坐标 $x$ 和 $y$ 有一个大于 1 的公约数 $g = \gcd(x,y)$ ，那么点 $(x/g, y/g)$ 就是一个在原点和 $(x,y)$ 之间的整数点，它会挡住观察者的视线。因此，点 $(x,y)$ 可见的充要条件是 $\gcd(x,y) = 1$ 。

2. 问题转化

问题转化为：在一个 $(N-1) \times (N-1)$ 的网格区域中（坐标从 $0$ 到 $N-1$ ），有多少个点 $(x,y)$ 满足 $\gcd(x,y) = 1$ ，且 $x,y$ 不同时为 $0$ 。

3. 利用对称性求解

由于方阵是正方形，问题具有对称性。我们可以分开统计：

坐标轴上的点：
- 在 $x$ 轴上，满足 $\gcd(x,0)=1$ 的点只有 $(1,0)$ 。
- 在 $y$ 轴上，满足 $\gcd(0,y)=1$ 的点只有 $(0,1)$ 。
- 这两个点是肯定可见的。
对角线上的点：
- 在 $y=x$ 的对角线上，满足 $\gcd(x,x)=1$ 的点只有 $(1,1)$ 。
- 这个点也是肯定可见的。
其他区域的点：
- 除去坐标轴和对角线，剩下的区域被对角线 $y=x$ 分为两个完全对称的部分（一个满足 $y<x$ ，另一个满足 $y>x$ ）。
- 我们只需要计算其中一部分（例如 $1 \le y < x \le N-1$ ）的可见点数量，然后乘以 2 即可。
- 对于一个固定的 $x$ （ $x > 1$ ），我们需要找有多少个 $y$ ( $1 \le y < x$ ) 满足 $\gcd(x,y)=1$ 。这个数量正好是欧拉函数 $\phi(x)$ 的定义（因为当 $x>1$ 时, $\gcd(x,x) \ne 1$ ，所以统计 $y \in [1, x-1]$ 和 $y \in [1, x]$ 的结果是一样的）。
- 所以，在 $1 \le y < x \le N-1$ 区域内，可见点的总数是 $\sum_{i=2}^{N-1} \phi(i)$ 。

4. 最终公式

综合以上几部分，可见学生的总数为：

$N=1$ 时，方阵里没有学生，答案为 $0$ 。
$N \ge 2$ 时，总数 = (坐标轴上的点) + (对角线上的点) + (其他区域的点) $= 2 + 1 + 2 \cdot \sum_{i=2}^{N-1} \phi(i) = 3 + 2 \cdot \sum_{i=2}^{N-1} \phi(i)$

5. 算法实现

为了计算 $\sum \phi(i)$ ，我们需要高效地求出 $1$ 到 $N-1$ 的所有欧拉函数值。这可以通过线性筛在 $\mathcal{O}(N)$ 的时间内完成。

写一个线性筛，预处理出 $1$ 到 $N-1$ 的所有 $\phi$ 值。
根据公式，累加 $\phi(2)$ 到 $\phi(N-1)$ 的值并计算最终结果。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

const int MAXN = 40005;
int phi[MAXN];
int primes[MAXN], cnt;
bool is_prime[MAXN];

void euler_sieve(int n) {
    fill(is_prime, is_prime + n + 1, true);
    is_prime[0] = is_prime[1] = false;
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            primes[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < cnt && i * primes[j] <= n; j++) {
            is_prime[i * primes[j]] = false;
            if (i % primes[j] == 0) {
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            } else {
                phi[i * primes[j]] = phi[i] * (primes[j] - 1);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    if (n == 1) {
        cout << 0 << endl;
        return 0;
    }

    euler_sieve(n - 1);

    long long sum_phi = 0;
    for (int i = 2; i < n; i++) {
        sum_phi += phi[i];
    }

    cout << 2 * sum_phi + 3 << endl;

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    static final int MAXN = 40005;
    static int[] phi = new int[MAXN];
    static int[] primes = new int[MAXN];
    static boolean[] is_prime = new boolean[MAXN];
    static int cnt = 0;

    public static void eulerSieve(int n) {
        Arrays.fill(is_prime, true);
        is_prime[0] = is_prime[1] = false;
        phi[1] = 1;
        for (int i = 2; i <= n; i++) {
            if (is_prime[i]) {
                primes[cnt++] = i;
                phi[i] = i - 1;
            }
            for (int j = 0; j < cnt && (long) i * primes[j] <= n; j++) {
                is_prime[i * primes[j]] = false;
                if (i % primes[j] == 0) {
                    phi[i * primes[j]] = phi[i] * primes[j];
                    break;
                } else {
                    phi[i * primes[j]] = phi[i] * (primes[j] - 1);
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        if (n == 1) {
            System.out.println(0);
            return;
        }

        eulerSieve(n - 1);

        long sumPhi = 0;
        for (int i = 2; i < n; i++) {
            sumPhi += phi[i];
        }

        System.out.println(2 * sumPhi + 3);
    }
}

import sys

def euler_sieve(n):
    phi = list(range(n + 1))
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    primes = []
    phi[1] = 1

    for i in range(2, n + 1):
        if is_prime[i]:
            primes.append(i)
            phi[i] = i - 1
        
        for p in primes:
            if i * p > n:
                break
            is_prime[i * p] = False
            if i % p == 0:
                phi[i * p] = phi[i] * p
                break
            else:
                phi[i * p] = phi[i] * (p - 1)
    return phi

def main():
    n = int(sys.stdin.readline())

    if n == 1:
        print(0)
        return

    phi_values = euler_sieve(n - 1)
    
    sum_phi = 0
    for i in range(2, n):
        sum_phi += phi_values[i]
        
    print(2 * sum_phi + 3)

if __name__ == "__main__":
    main()

算法及复杂度

算法：欧拉函数 + 线性筛
时间复杂度：使用线性筛预处理欧拉函数表的时间复杂度为 $\mathcal{O}(N)$ 。计算总和的循环也是 $\mathcal{O}(N)$ 。因此，总时间复杂度为 $\mathcal{O}(N)$ 。
空间复杂度：需要一个数组来存储欧拉函数值以及线性筛所需的辅助数组，空间复杂度为 $\mathcal{O}(N)$ 。