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

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; }


相关文章:
数学1
POJ2478 ?题目大意: ?求所有分母不大于 n 的既约真分数个数 ?算法思路: ?分母为 x 的既约真分数有φ (x)个 ?分母不大于 n 的既约真分数个数为 φ (...
更多相关标签:
2478趣吧 | www.2478.com | lpc2478 | bixolon 2478bsc驱动 | vx2478smhd | 2478平台 | 优派vx2478 | 优派vx2478评测 |