問題
n の真の約数とは、n 自身を除く正の約数のことです。その和を n と比べて、和の方が大きければ過剰数、等しければ完全数、小さければ不足数です。たとえば 12 の真の約数は 1, 2, 3, 4, 6 で、和は 16 になるので、12 は過剰数です。
abundant_perfect_deficient(n) を実装してください。
n は最大 10^12 にもなるので、n 未満の数を 1 つずつ調べていては時間がかかりすぎます。約数は d と n / d のペアになっているので、d は √n まで試せば十分です。
入力
n: 分類する数。
出力
文字列 "abundant"、"perfect"、"deficient" のいずれかを小文字で返してください。1 には真の約数がない(和は 0)ので、不足数です。
制約
1 ≤ n ≤ 10^12
例
入力:
n = 28
期待される出力:
expected = "perfect"
入力:
long long n = 28;
期待される出力:
std::string expected = "perfect";
入力:
long n = 28;
期待される出力:
string expected = "perfect";
解説
真の約数 1 + 2 + 4 + 7 + 14 の和は 28 なので、答えは "perfect" です。
入力:
n = 15
期待される出力:
expected = "deficient"
入力:
long long n = 15;
期待される出力:
std::string expected = "deficient";
入力:
long n = 15;
期待される出力:
string expected = "deficient";
解説
真の約数 1 + 3 + 5 の和は 9 で、15 より小さいので、答えは "deficient" です。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
d が n を割り切るなら n / d も n を割り切ります。d は d × d ≤ n の間だけ回しましょう。
ヒント 2
d × d = n のときは、d を 2 回ではなく 1 回だけ足します。
ヒント 3
和に n 自身を含めないこと、そして n = 1 を別に扱うことを忘れないようにしましょう。
目安の計算量
時間 O(√n)、追加メモリ O(1)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。