题目
题目描述
作为体育委员，C君负责这次运动会仪仗队的训练。
仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。
现在，C君希望你告诉他队伍整齐时能看到的学生人数。
输入描述
共一个数N。
输出描述
共一个数，即C君应看到的学生人数。
示例1
输入
4
输出
9
备注
对于 100% 的数据，\(1 \le N \le 40000\)
题解
知识点：欧拉函数，筛法。
经典老题。
不妨关注下三角区域，上三角区域答案是一样的。
我们以左下角为 \((0,0)\) 原点，发现 \(x \geq 2\) 的每列的答案为 \(\varphi(x)\) ，因为当且仅当横纵坐标互质时，这个点不会被任何点遮挡（不存在一个点的它的约数）。\(x = 1\) 时，答案为 \(\varphi(1) + 1\) ，因为特判 \(y=0\) 的情况。
最后，还要减去对角线的重复情况，答案为 \(\displaystyle 2+2\sum_{i=1}^{n-1} \varphi(i) - 1\) ， \(n=1\) 时答案特判为 \(0\) 。
欧拉函数可以通过线性筛得到。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 40007;
bool vis[N];
vector<int> prime;
int phi[N];
void get_euler(int n) {
phi[1] = 1;
for (int i = 2;i <= n;i++) {
if (!vis[i]) {
prime.push_back(i);
phi[i] = i - 1;
}
for (auto j : prime) {
if (i * j > n)break;
vis[i * j] = 1;
if (!(i % j)) {
phi[i * j] = j * phi[i];
break;
}
phi[i * j] = (j - 1) * phi[i];
}
}
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
get_euler(n - 1);
int ans = 0;
for (int i = 1;i <= n - 1;i++) ans += phi[i];
ans = ans * 2 + (n >= 2);
cout << ans << '\n';
return 0;
}