洛谷 P2158 [SDOI2008]仪仗队
洛谷 P2158 [SDOI2008]仪仗队
传送门
思路
从\((0，0)\)开始，抛开可以看到的\((0,1),(1,0),(1,1)\)三个点,做出一个\(5*5\)的矩阵试一下，发现当每个点的斜率的分母和分子互质时，这个点才能被看到（\(y==x\)时除外，因为已经被\((1,1)\)点挡住了），所以我们可以求欧拉函数累加，最后再加上原先的\((0,1),(1,0),(1,1)\)三个点，因为是从\(0\)开始的所以求到\(n-1\)就好了，需要注意的是\(ans\)需要乘以二，因为我们求的只是被\(y=x\)这条线分开的半个部分的可以看到的数量，而上下对称，所以直接乘二，最后的答案就是\(ans * 2 + 3\)
代码
#include <bits/stdc++.h>
#define N 40011
using namespace std;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return x * f;
}
int n, phi[N];
//求欧拉函数
void enlur(int n) {
for(int i = 2; 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);
}
}
}
}
int main() {
n = read();
if(n == 1) {
cout << '0';
return 0;
}
enlur(n - 1);
int ans = 0;
for(int i = 2; i <= n - 1; i++) {
ans += phi[i];
}
cout << ans * 2 + 3 << '\n';
return 0;
}
