SDOI2009 仪仗队

数论

Luogu

题目默认的是以 $(1,1)$ 为左下角，所以一个点 $(x,y)$ 到左下角连线的斜率为 $\frac{y-1}{x-1}$。已知如果两个点到起点的连线斜率相等，就会互相抵挡，所以那些能被看到的点要求在其前面的点连线的斜率没有与它的斜率相等的。那么就是要求 $\frac{y-1}{x-1}$ 是一个既约分数。等于 $y-1$ 与 $x-1$ 互质。但是这个仪仗队的对角线以上以下是对称的，所以只要求出一半的答案，再加上那些一开始就会被看到的点数。最终答案为$2*\sum_{i=2}^{n-1} \varphi(i)+3$，注意特判一下 $n=1​$ 的情况。

#include <iostream>
#include <cstdio>
const int MAXN = 4e4;
int n, ans, tot;
int phi[MAXN | 1], prime[MAXN | 1];
bool vis[MAXN | 1];
int main() {
    scanf("%d", &n);
    phi[1] = 1;
    for(int i = 2; i <= n; ++i) {
        if(!vis[i]) {
            prime[++tot] = i;
            phi[i] = i - 1;
        }
        for(int j = 1; j <= tot && i * prime[j] <= n; ++j) {
            vis[i * prime[j]] = true;
            if(i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            } else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
    for(int i = 2; i < n; ++i) ans += phi[i];
    printf("%d\n", ans ? ans * 2 + 3 : 0);
    return 0;
}