当前位置:首页 >> 学科竞赛 >>

poj2478


#include<cstdio> #define?XMAX?1000100 #define?ll?long?long?int using?namespace?std; int?phi[XMAX+100]; int?szm[XMAX+100]; int?szp[XMAX+100]; ll?szs[XMAX+100]; int?totp; void?init() { in

t?f1; int?f2; for(f1=2;f1<=XMAX;f1++) { if(szm[f1]==0) { szm[f1]=f1; szp[++totp]=f1; phi[f1]=f1?1; } for(f2=1;(f2<=totp)&&(szp[f2]<=szm[f1])&&((ll)szp[f2]*f1<=XMAX);f2++) { szm[szp[f2]*f1]=szp[f2]; if(szp[f2]==szm[f1]) phi[szp[f2]*f1]=phi[f1]*szp[f2]; else phi[szp[f2]*f1]=phi[f1]*(szp[f2]?1); } } for(f1=2;f1<=XMAX;f1++) szs[f1]=szs[f1?1]+phi[f1]; return; } int?main() { int?zhi; init(); for(;;) { scanf("%d\n",&zhi); if(zhi==0) break; printf("%lld\n",szs[zhi]); } return?0; }


相关文章:
更多相关标签: