洛谷 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;
}