SternBrocot Tree [HDU 4556]

http://acm.hdu.edu.cn/showproblem.php?pid=4556

//就是求有多少个分数,对于分母i求N以内与其互质的数的个数，其实就是欧拉函数
const int MM = 1000000+10;
typedef __int64 ll; 
int N; 
ll phi[MM], sum[MM];

void get_phi() {
     ll i,j,k;
     for(i=1;i<MM;i++) phi[i]=i;
     for(i=2;i<MM;i+=2) phi[i]>>=1;
     for(i=3;i<MM;i++) {
         if(phi[i]==i) {
             for(j=i;j<MM;j+=i) 
                 phi[j]=phi[j]/i*(i-1);
         }
     }
     sum[0]=0;
     for(i=1;i<MM;i++) sum[i]=sum[i-1]+(phi[i]<<1);
}
void solve() { 
    printf("%I64d\n",sum[N]+1);
}
int main() {
    get_phi(); 
    while(scanf("%d",&N)!=EOF) solve();
    return 0;
}