問題
真の約数(その数自身を除く約数)の和がその数より大きいとき、その数を過剰数といいます。最小の過剰数は 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
例
入力:
limit = 23
期待される出力:
expected = 276
入力:
long long limit = 23;
期待される出力:
long long expected = 276;
入力:
long limit = 23;
期待される出力:
long expected = 276;
解説
23 以下の数はどれも2つの過剰数の和で表せないので、すべて数えます。1 + 2 + ... + 23 = 276 です。
入力:
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用に調整されています。上記の説明と制約に従ってください。