すべてのチャレンジ
難しい 0件解決済み 正答率0%

2つの過剰数の和で表せない数

上限以下の数のうち、2つの過剰数の和で表せないものを合計します。

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

  • 篩を使って範囲内の約数の和を求められる
  • 真偽値の配列で作れる和に印を付けられる
  • 和が上限を超えたら二重ループを早めに打ち切れる

問題

原文(英語)を表示

真の約数(その数自身を除く約数)の和がその数より大きいとき、その数を過剰数といいます。最小の過剰数は 12 で、1 + 2 + 3 + 4 + 6 = 16 です。2つの過剰数の和で表せる数(24 = 12 + 12 のように、同じ数を2回使ってもかまいません)もあれば、表せない数もあります。1 から limit までの正の整数のうち、表せないものをすべて足し合わせてください。

non_abundant_sums(limit) を実装してください。

篩を使ってすべての数の約数の和を一度に求め、過剰数を列挙してから、上限以下に収まる2つの過剰数の和すべてに印を付けていきます。

入力

limit:調べる最大の数。

出力

1 ≤ n ≤ limit を満たし、2つの過剰数の和で表せないすべての n の和を返してください。

制約

1 ≤ limit ≤ 10,000

例

例 1
入力:
limit = 23

期待される出力:
expected = 276
入力:
long long limit = 23;

期待される出力:
long long expected = 276;
入力:
long limit = 23;

期待される出力:
long expected = 276;

解説

23 以下の数はどれも2つの過剰数の和で表せないので、すべて数えます。1 + 2 + ... + 23 = 276 です。

例 2
入力:
limit = 30

期待される出力:
expected = 411
入力:
long long limit = 30;

期待される出力:
long long expected = 411;
入力:
long limit = 30;

期待される出力:
long expected = 411;

解説

24 = 12 + 12 と 30 = 12 + 18 が除かれるので、答えは 465 − 24 − 30 = 411 です。

解き方のヒント

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

各 i について、2i, 3i, 4i, ... の約数の和に i を足します。

ヒント 2

過剰数を小さい順に集めます。

ヒント 3

a ≤ b となる各ペアについて、a + b が上限を超えたら内側のループを止めます。

目安の計算量

時間 O(limit log limit + A²)(A は過剰数の個数)、追加メモリ O(limit)

参考資料

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

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

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

他の人の解答から学ぶ

コミュニティの解答

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