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