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$即为答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#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;
}
------ 本文结束 ------