読者です 読者をやめる 読者になる 読者になる

UVa382 Perfection

問題
完全数かどうかを判定する問題。AOJ にも AtCoder Beginner Contest にもほぼ同じ問題がある。

#include <cstdio>

using namespace std;

int main() {
  
  int N;
  puts("PERFECTION OUTPUT");
  while(scanf("%d", &N) && N) {
    
    printf("%5d  ", N);
    
    int sum = 0;
    for(int i=1; i*i<N; i++) {
      if(N % i == 0) {
        sum += i;
        sum += N/i;
      }
    }
    
    sum -= N;
    
    if(sum < N) { puts("DEFICIENT"); }
    else if(sum == N) { puts("PERFECT"); }
    else { puts("ABUNDANT"); }
  }
  puts("END OF OUTPUT");
  
  return 0;
}

メモ
初めに出力を見て、完全数を判定するだけの問題だと考えた。この問題は過去に二度は見ていると思った。イメージが強いのはAOJの問題であった。制約が大きいことを理由に O(sqrt(N)) で解いたというイメージが強かった。次に完全数とは何であったかを、忘れていたので考えた。サンプルを説明する文を読む限り、素因数や約数が関係するものかと考えた。"DEFICIENT" と "ABUNDANT" があるので素因数や約数が不足か過剰かであるということ、"PERFECT" が過不足がないということを思い出した。1を入れた素因数と約数と、どちらであるかと考えた。素因数としてコードを書いてみて、サンプルの出力と異なるので、約数を求めればよいのだと分かった。