# [洛谷 2158][SDOI2008] 仪仗队【欧拉函数】

• 2018-03-01
• 0
• 0

`4`

`9`

## Code: O(N) [2363K, 0MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int N, phi[40002], prime[40002], pcnt;
bool isprime[40002];

inline void calc_phi(int upr){
memset(isprime, 1, sizeof(isprime)), pcnt = 0;
for(register int i = 2; i <= upr; i++){
if(isprime[i]) prime[++pcnt] = i, phi[i] = i - 1;
for(register int j = 1; j <= pcnt && i * prime[j] <= upr; j++){
isprime[i * prime[j]] = 0;
if(i % prime[j] == 0){
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
else phi[i * prime[j]] = phi[i] * phi[prime[j]];
}
}
}

int main(){
scanf("%d", &N);
if(N == 1) return puts("0"), 0;  // Special judge for N == 1
calc_phi(--N);
int ans = 0;
for(register int i = 2; i <= N; i++) ans += phi[i];
printf("%d\n", ans * 2 + 3);
return 0;
}
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai