[SDOI2008] 仪仗队
作为体育委员,C 君负责这次运动会仪仗队的训练。仪仗队是由学生组成的 $N \times N$ 的方阵,为了保证队伍在行进中整齐划一,C 君会跟在仪仗队的左后方,根据其视线所及的学生人数来判断队伍是否整齐(如下图)。
现在,C 君希望你告诉他队伍整齐时能看到的学生人数。
对于 $100 \%$ 的数据,$1 \le N \le 40000$。
think
设$C$ 君 位于 $(1,1)$
那么 他看到的 每一个人 他的斜率一定是 唯一的
也就是 不能看到斜率相同的两个人
设 被看到的人的坐标是 $(x,y)$
那么$(x,y)=1$
用 反证法
如果$(x,y)=g$ 那么 $k_{x,y}=k_{\frac xg ,\frac yg}$
那么 $(x,y)$ 就一定不会被看到
那么我们 枚举
$$
\begin {align}
设phi_i 为[2,i]内与 i 互质的数量\\
i \in [1,n]\\
ans:ans+phi_i
\end {align}
$$
很显然$phi$ 就是一个 积性函数
观察数据范围我们 直接用 $O(nlogn)$ 的筛法来求出积性函数了
code
// Luogu P2158 [SDOI2008] 仪仗队
// https://www.luogu.com.cn/problem/P2158 2024-03-13 15:27:00
#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, m;
constexpr int N = 4E5 + 10;
int phi[N];
void solve() {
cin >> n;
cin >> n;
if (n == 1) {
cout << "0\n";
return;
} else {
int ans = 0;
for (int i = 1; i <= n; i++) phi[i] = i;
for (int i = 2; i <= n; i++) {
if (phi[i] == i) {
for (int j = i; j <= n; j += i) {
phi[j] = phi[j] / i * (i - 1);
}
}
}
for (int i = 2; i < n; i++) ans += 2 * phi[i];
cout << ans + 3 << "\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
return 0;
}