luogu P2158 [SDOI2008]仪仗队 （欧拉函数）

#include <cstdio>
using namespace std;
const int N = 40010;
typedef long long ll;
ll phi[N];
int n;

inline void GetPhi() {
    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;
            }
}

int main() {
    scanf("%d", &n);
    GetPhi();
    ll ans = 0;
    for (int i = 2; i < n; i++)
        ans += phi[i];
    ans *= 2;
    if (n >= 2)    ans += 3;
    printf("%lld", ans);
    return 0;
}