作为体育**，C 君负责这次运动会仪仗队的训练。仪仗队是由学生组成的 的方阵，为了保证队伍在行进中整齐划一，C 君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐（如下图）。 现在，C 君希望你告诉他队伍整齐时能看到的学生人数。 输入 一行，一个正整数 。 输出 输出一行一个数，即 C 君应看到的学生人数。 样例输入 复制 4 样例输出 复制 9 提示 对于 的数据， 。

这个问题是求在 \( n \times n \) 的方阵中，从坐标 \((0,0)\) 的位置（左下角）能看到多少个格点（学生），不包括 C 君自己所在的位置 \((0,0)\)。 --- 分析 C 君在 \((0,0)\)，能看到一个学生 \((x,y)\) 的条件是： 1. \( 1 \le x \le n \)，\( 1 \le y \le n \)（因为方阵从 1 到 n 编号，但这里我们按坐标从 0 到 n 考虑更方便，不过题目是 \(n\) 表示方阵大小，学生坐标从 1 到 n）。 2. \(\gcd(x, y) = 1\)（即 \(x\) 与 \(y\) 互质），否则会被更靠近原点的人挡住。 3. 并且 C 君自己站在 \((0,0)\) 不算在内。 --- 数学化 设 \(n\) 为方阵大小（学生坐标从 1 到 n）。 能看到的点的数量为： \[ \sum_{x=1}^{n} \sum_{y=1}^{n} [\gcd(x, y) = 1] \] 但这样会重复计算对称的点，并且 C 君在左下角，视线是向右上方向看的，所以其实我们只需要考虑 \(x\) 与 \(y\) 互质且 \(x \ge 1, y \ge 1\) 的点，并且这些点都在 \(n \times n\) 范围内。 实际上更简单： 能看到的点就是所有满足 \(1 \le x, y \le n\) 且 \(\gcd(x, y) = 1\) 的 \((x, y)\) 的数量。 --- 对称性 因为方阵是对称的，且 C 君在左下角，所以能看到的点包括： - 第一行 \(y=1\)：\(n\) 个点（除了 \((1,1)\) 吗？等一下，\((1,1)\) 的 \(\gcd=1\)，也能看到，但 C 君在 (0,0)，(1,1) 是第一个学生，也能看到）。 - 第一列 \(x=1\)：\(n\) 个点，但 \((1,1)\) 已经算过。 - 其他区域 \(2 \le x \le n, 2 \le y \le n\) 且 \(\gcd=1\) 的点。 其实更直接的方法： 能看到的点的总数 = \[ 2 + \sum_{x=2}^{n} \varphi(x) \] 不对，我们重新推导。 --- 标准推导 从 (0,0) 看，能看到一个点 (x,y) 当且仅当 \(\gcd(x, y) = 1\)。 坐标范围：\(1 \le x \le n, 1 \le y \le n\)。 总数 = \[ \sum_{x=1}^{n} \sum_{y=1}^{n} [\gcd(x, y) = 1] \] 利用对称性和欧拉函数： 当 \(x=1\) 时，\(y=1\) 到 \(n\) 都互质，有 \(n\) 个点。 当 \(y=1\) 时，\(x=1\) 到 \(n\) 都互质，有 \(n\) 个点，但 (1,1) 重复计算了一次。 所以第一行+第一列（除去重叠）有 \(2n - 1\) 个点。 对于 \(x \ge 2, y \ge 2\) 且 \(\gcd(x, y)=1\) 的点，数量为： \[ \sum_{x=2}^{n} \sum_{y=2}^{n} [\gcd(x, y) = 1] \] 但更常用的是： 总数 = \[ \sum_{x=1}^{n} 2\varphi(x) - 1 \] 其中 \(\varphi(x)\) 是欧拉函数，表示 \(1 \le y \le x\) 中与 \(x\) 互质的 \(y\) 的数量。 这个公式的来源： 对于每个斜率 \(y/x\)，第一次出现的互质对 \((x,y)\) 会被看到，对称的 \((y,x)\) 也会被看到，但 \(x=y\) 时只算一次。 实际上经典公式（原题是仪仗队问题，来自 NOI 2002 或类似）： 从 (0,0) 看 \(n \times n\) 的格点（坐标从 0 到 n-1 或 1 到 n 需注意），能看到的点的数量（包括自己）是： \[ 1 + 2 \sum_{x=1}^{n-1} \varphi(x) \] 当坐标从 1 到 n 时，公式为： \[ \text{ans} = 2 \sum_{x=1}^{n} \varphi(x) - 1 \] 但要注意，当 \(n=1\) 时，只能看到自己，输出 0（因为 C 君自己不算学生）。 --- 验证样例 \(n=4\)： \(\varphi(1)=1, \varphi(2)=1, \varphi(3)=2, \varphi(4)=2\) \[ 2 \times (1+1+2+2) - 1 = 2 \times 6 - 1 = 12 - 1 = 11 \] 但样例输出是 9，说明我的公式可能坐标范围理解有误。 --- 检查坐标 题目说“\(n \times n\) 的方阵”，C 君在左后方，即左下角 (0,0)，学生坐标从 (1,1) 到 (n,n)。 那么能看到的点 (x,y) 满足 \(1 \le x \le n, 1 \le y \le n\) 且 \(\gcd(x,y)=1\)。 我们数一下 \(n=4\)： (1,1) gcd=1 ✅ (1,2) ✅ (1,3) ✅ (1,4) ✅ (2,1) ✅ (2,2) gcd=2 ❌ (2,3) gcd=1 ✅ (2,4) gcd=2 ❌ (3,1) ✅ (3,2) ✅ (3,3) gcd=3 ❌ (3,4) gcd=1 ✅ (4,1) ✅ (4,2) gcd=2 ❌ (4,3) gcd=1 ✅ (4,4) gcd=4 ❌ 数 ✅： (1,1),(1,2),(1,3),(1,4) → 4 (2,1),(2,3) → 2 (3,1),(3,2),(3,4) → 3 (4,1),(4,3) → 2 总共 \(4+2+3+2 = 11\) 但样例输出是 9，说明我理解错了。 --- 再看图 C 君在左后方，跟在仪仗队左后方，视线方向是右前方，可能学生是从 (1,1) 到 (n,n)，但 C 君在 (0,0) 看，如果学生是站在整数格点上，那么 (1,1) 会挡住 (2,2) 等。 但样例 n=4 输出 9，说明可能学生是站在格子内部，而不是格点上？ 不，常见问题“仪仗队”是 SDOI 2008 的“可见点”问题： 在 \(n \times n\) 的格点（从 (0,0) 到 (n,n)）中，从 (0,0) 能看到多少个点（不包括自己）？ 公式： \[ \text{ans} = \sum_{x=1}^{n} \sum_{y=1}^{n} [\gcd(x, y) = 1] \] 但这样 n=4 时： x=1: y=1..4 → 4 x=2: y=1,3 → 2 x=3: y=1,2,4 → 3 x=4: y=1,3 → 2 总和 11，不是 9。 --- 可能的原因 题目中“方阵 \(n \times n\)”可能是指有 n 行 n 列学生，最左下角学生坐标是 (1,1)，最右上角是 (n,n)，C 君在 (0,0)。 那么能看到的点 (x,y) 满足 \(1 \le x,y \le n\) 且 \(\gcd(x,y)=1\)。 但这样 n=4 得 11，不是 9。 所以可能是：C 君在 (0,0)，学生从 (1,1) 到 (n,n)，但 C 君的视线是向右上方向，所以如果 x 与 y 不互质，则会被 (x/g, y/g) 挡住。 但这样还是 11。 --- 我怀疑样例解释 可能 n=4 时，学生是站在 (0,0) 到 (3,3) 的 4×4 格点阵（16个点），C 君在 (-1,-1) 之类？但题目说左后方，可能 C 君在 (0,0)，学生从 (1,1) 到 (4,4)？ 我们试 n=4，学生坐标 (1..4,1..4)，从 (0,0) 看： 可见点： (1,1),(1,2),(1,3),(1,4) (2,1),(2,3) (3,1),(3,2),(3,4) (4,1),(4,3) 共 11 个。 但答案是 9，说明可能学生是站在 (0,0) 到 (n-1,n-1) 的 n×n 个点，C 君在 (-1,-1) 吗？ --- 查一下原题 这是经典问题“仪仗队”，来自洛谷 P2158。 题目中 n 是方阵大小，学生从 (0,0) 到 (n-1,n-1) 共 n×n 个点，C 君在 (0,0) 位置（他是观察者，不算在内）。 那么能看到的点 (x,y) 满足 \(0 \le x,y \le n-1\)，且 \(\gcd(x,y)=1\)，但 (0,0) 不算，且 (0,1) 和 (1,0) 等也算。 公式： \[ \text{ans} = 2 \sum_{x=1}^{n-1} \varphi(x) + 1 \quad (\text{当 } n>1) \] 当 n=1 时，ans=0。 验证 n=4： \(\varphi(1)=1, \varphi(2)=1, \varphi(3)=2\) \[ 2 \times (1+1+2) + 1 = 2 \times 4 + 1 = 9 \] 匹配样例输出 9。 --- 所以正确公式 当 \(n=1\)，输出 0。 当 \(n>1\)，输出： \[ 2 \sum_{i=1}^{n-1} \varphi(i) + 1 \] --- 代码实现 用欧拉筛预处理欧拉函数，然后计算前缀和。 ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; if (n == 1) { cout << 0 << endl; return 0; } vector<int> phi(n + 1); vector<int> primes; vector<bool> is_prime(n + 1, true); phi[1] = 1; for (int i = 2; i <= n; i++) { if (is_prime[i]) { primes.push_back(i); phi[i] = i - 1; } for (int p : 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); } } } long long ans = 1; // 对应 (1,0) 和 (0,1) 的对称计算后加1 for (int i = 1; i < n; i++) { ans += 2 * phi[i]; } cout << ans << endl; return 0; } ``` [2026-01-20 17:26:42 | AI问答 | 2871点数解答]