Bzoj 2190(欧拉函数)

Bzoj 2190
由题意可知，能看见的人是对角线对称的
斜率相同的直线中只有一条能被看见，也就是说$\frac{y_1}{x_1}=\frac{y_2}{x_2}$的直线只有一条能被看见。
如果$gcd(x, y)=d≠1$的话，$\frac{y}{x}$可约分，就肯定被前面的点$(\frac{x}{d},\frac{y}{d})$挡住盖了，所以$gcd(x, y)=1$的点才能被看见。我们这里用欧拉函数求。因为欧拉函数$\varphi(x)$就是小于$x$与$x$互质的数，那这里求出$2\sum_{i=1}^{n-1}\varphi(i)+1$即为答案

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 40000 + 5;
int n;
int phi[MAXN];
void getphi(int n) {
    for (int i = 1; i <= n; i++) phi[i] = 0;
    phi[1] = 1;
    for (int i = 2; i <= n; i++) if (!phi[i]) {
        for (int j = i; j <= n; j += i) {
            if (!phi[j]) phi[j] = j;
            phi[j] = phi[j] / i * (i - 1);
        }
    }
}
void clean() {}
void solve() {
    clean();
    getphi(n);
    int tot = 0;
    for (int i = 1; i < n; i++) tot += phi[i];
    printf("%d\n", tot * 2 + 1);
}
int main() {
    #ifndef ONLINE_JUDGE 
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    while (scanf("%d", &n) == 1) solve();
    return 0;
}