BZOJ2190 – [SDOI2008]仪仗队

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
38
39
40
41
42
43



#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int MAX_N = 50000;
typedef unsigned long long ULL;
int iscomps[MAX_N];
int prime[MAX_N]; int ppos;
ULL phi[MAX_N];


void gen_prime(int up) {
    phi[1] = 1;
    for(int i=2;i<up;i++) {
        if(!iscomps[i]) {
            prime[ppos++] = i;
            phi[i] = i - 1;
        }

        for(int j=0;j<ppos&&i*prime[j]<up;j++) {
            iscomps[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            } else {
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
            }
        }
    }
}

int main() {
    gen_prime(MAX_N);

    int q; scanf("%d", &q);
    ULL ans = 0;
    for(int i=1;i<q;i++) {
        ans += phi[i];
    }

    ans = ans * 2 + 1;
    printf("%lldn", ans);
}