中級 0件解決済み 正答率0%

友愛数

2 つの数がどちらも上限以下である友愛数の組を、すべて列挙します。

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

  • 上限までのすべての数について、真の約数の和の表を作る
  • 組の条件を両方向から確かめる
  • 同じ組を 2 回挙げたり、完全数を挙げたりしないようにする

問題

原文(英語)を表示

n の真の約数(n 自身を除く約数)の和を s(n) とします。異なる 2 つの数 a と b が s(a) = b かつ s(b) = a を満たすとき、a と b を友愛数の組といいます。最小の組は 220 と 284 で、s(220) = 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284、s(284) = 1 + 2 + 4 + 71 + 142 = 220 です。

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

limit までのすべての n について s(n) を 1 つずつ計算すると時間がかかります。ふるいを使う方が効率的です。各 d について、d より大きい d の倍数すべてに d を足していきます。

入力

limit: 組に含まれる数がとりうる最大値。

出力

a < b ≤ limit を満たす組 [a, b] のリストを、a の昇順に並べて返してください。2 つの数がどちらも limit 以下である組だけを含めます。完全数(s(n) = n となる数)は組になりません。1 組もなければ空のリストを返してください。

制約

1 ≤ limit ≤ 200,000

例

例 1
入力:
limit = 1500

期待される出力:
expected = [
    [220, 284],
    [1184, 1210]
]
入力:
long long limit = 1500;

期待される出力:
std::vector<std::vector<long long>> expected = {
    {220, 284},
    {1184, 1210}
};
入力:
long limit = 1500;

期待される出力:
long[][] expected = new long[][] {
    new long[] {220, 284},
    new long[] {1184, 1210}
};

解説

s(220) = 284、s(284) = 220、そして s(1184) = 1210、s(1210) = 1184 です。どちらの組も 1500 以下に収まります:[[220, 284], [1184, 1210]]。

例 2
入力:
limit = 250

期待される出力:
expected = []
入力:
long long limit = 250;

期待される出力:
std::vector<std::vector<long long>> expected = {};
入力:
long limit = 250;

期待される出力:
long[][] expected = new long[][] {};

解説

220 は 250 以下ですが、相手の 284 は 250 を超えるので、条件を満たす組はありません:[]。

解き方のヒント

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

ヒント 1

1 から limit / 2 までの各 d について、2d, 3d, 4d, … の和に d を足していきます。

ヒント 2

各 a について、その約数の和を b とし、b が範囲内にあり、b の約数の和が a になるかを確かめます。

ヒント 3

a < b という条件を付ければ、各組を 1 回だけ挙げられ、完全数も除けます。

目安の計算量

時間 O(limit log limit)、追加メモリ O(limit)

参考資料

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

ランキング

全体ランキング

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

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

他の人の解答から学ぶ

コミュニティの解答

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