题目连接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=284
这道题得数据范围是60000,询问为100组,所以我感觉暴力也可以,不过我并没有这么写,我利用的是数论的那个因子和的规律来求解的
解法类似于ZOJ 2095,详细内容参见:http://blog.csdn.net/xieshimao/archive/2011/05/06/6399672.aspx
我的代码:
#include<stdio.h> #include<string.h> bool flag[300]; int prime[300]; void init() { int i,j,num=0; memset(flag,0,sizeof(flag)); for(i=2;i<300;i++) { if(!flag[i]) { prime[num++]=i; for(j=i*i;j<300;j=j+i) flag[j]=true; } } } void slove(int n) { int i,N=n,k1,k2,ans=1; for(i=0;prime[i]*prime[i]<=n;i++) { k1=1,k2=0; if(n%prime[i]==0) { n=n/prime[i]; k1=k1*prime[i]; k2=k2+k1; while(n%prime[i]==0) { n=n/prime[i]; k1=k1*prime[i]; k2=k2+k1; } ans=ans*(k2+1); } if(n==1) break; } if(n>1) ans=ans*(n+1); ans=ans-N; if(ans==N) printf("%5d PERFECT/n",N); else if(ans>N) printf("%5d ABUNDANT/n",N); else printf("%5d DEFICIENT/n",N); } int main() { int n; init(); printf("PERFECTION OUTPUT/n"); while(scanf("%d",&n)!=EOF) { if(n==0) break; slove(n); } printf("END OF OUTPUT/n"); return 0; }