すべてのチャレンジ
簡単 0件解決済み 正答率0%

過剰数・完全数・不足数

真の約数の和をもとに、数を過剰数・完全数・不足数のいずれかに分類します。

このチャレンジで学べること

  • O(√n) の時間で真の約数の和を求める
  • 平方根にあたる約数を 2 回数えないようにする
  • 比較の結果から 3 つのラベルのいずれかを返す

問題

原文(英語)を表示

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

例

例 1
入力:
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" です。

例 2
入力:
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用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。