PKU 1528 Perfection
http://poj.org/problem?id=1528
与えられた数が完全数かそうでないかを判定する問題。
AOJに似たような問題がありました。あれのO(n)解しか思い浮かばなかったことは悲しい思い出です。
int sum(int n){ int ret=0; for(int i=1;i*i<=n;i++){ if(n%i)continue; ret+=i+n/i; if(i*i==n)ret-=i; } return ret-n; } main(){ int n; cout<<"PERFECTION OUTPUT"<<endl; while(cin>>n,n){ printf("%5d ",n); int ss=sum(n); if(ss==n)cout<<"PERFECT"<<endl; else if(ss<n)cout<<"DEFICIENT"<<endl; else cout<<"ABUNDANT"<<endl; } cout<<"END OF OUTPUT"<<endl; }