トップページに戻る    次の競技プログラミングの問題へ    前の競技プログラミングの問題へ

ARC-026-B 完全数

■■■問題■■■

高橋君は完全なものが大好きです。

自然数には、完全数というものがあります。
完全数というのは、自分以外の約数の総和が自分と等しくなる自然数のことです。
例えば 6 の場合 1+2+3=6となるので完全数です。
それに対して、自分以外の約数の総和が自分より小さくなる場合は不足数と言い、
大きくなる場合は過剰数と言います。

高橋君には今気になっている自然数があります。
高橋君のために、それが完全数なのか不足数なのか過剰数なのか判定してください。

■■■入力■■■

N

1行目に高橋君が気になっている自然数N(1 <= N <= 100億)が与えられる。

■■■出力■■■

Nが完全数ならばPerfect、 不足数ならばDeficient、 過剰数ならばAbundant、を1行で出力せよ。


C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("6");
            //Perfect
            //1+2+3=6なので6は完全数です
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("24");
            //Abundant
            //1+2+3+4+6+8+12 > 24なので24は過剰数です。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("27");
            //Deficient
            //1+3+9 < 27なので27は不足数です。
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("945");
            //Abundant
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long N = long.Parse(InputList[0]);

        HashSet<long> YakusuuSet = DeriveYakusuuSet(N);

        long wkSum = YakusuuSet.Where(X => X != N).Sum();

        if (wkSum == N) Console.WriteLine("Perfect");
        if (wkSum < N) Console.WriteLine("Deficient");
        if (wkSum > N) Console.WriteLine("Abundant");
    }

    //約数のSetを求める
    static HashSet<long> DeriveYakusuuSet(long pTarget)
    {
        var WillReturn = new HashSet<long>();

        for (long I = 1; I * I <= pTarget; I++) {
            if (pTarget % I == 0) {
                WillReturn.Add(I);
                WillReturn.Add(pTarget / I);
            }
        }
        return WillReturn;
    }
}


解説

1からルート(N)まで、試し割りしてます。