【BZOJ 2190】[SDOI2008] 仪仗队

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2190
离线版题目：http://paste.ubuntu.com/20271981/

这个是“能量采集”的弱化版，所以mu和phi都可以很简单做
线筛写错了，wa了好久QAQ

#include<iostream>
#include<cstdio>
#include<bitset>
using namespace std;
 
const int MAXN = 40000+9;
 
int n,pri[MAXN],tot,phi[MAXN];
bitset<MAXN> tag;
 
inline void Get_Phi(){
    phi[1] = 1;
    for (int i=2;i<=n;i++){
        if (!tag[i]) pri[++tot] = i, phi[i] = i-1;
        for (int j=1;j<=tot && pri[j]*i<=n;j++) {
            tag[i*pri[j]] = 1;
            if (i % pri[j]) phi[i*pri[j]] = phi[i]*(pri[j]-1);
            else {phi[i*pri[j]] = phi[i]*pri[j]; break;} 
        }
    }
    for (int i=2;i<=n;i++) phi[i] += phi[i-1];
}
 
int main(){
    scanf("%d",&n); n-=1;
    Get_Phi();
    printf("%d\n",phi[n]*2-1+2);
    return 0;
}