フレンドリーナンバー -数理論によれば、フレンドリーナンバーとは、同じ存在指数を持つ2つ以上の数字です。
リッチネスインデックス - 自然数のリッチネスインデックスは、自然数のすべての約数の合計と自然数自体の比率として定義できます。
数値 n の存在量は、$\mathrm{\frac{\sigma(n)}{n}}$ として表すことができます。ここで、$\mathrm{\sigma(n)}$ は、すべての n 数の近似。
たとえば、自然数 30 の豊かさの指数は、
です。$$\mathrm{\frac{\sigma(30)}{30}=\frac{1 2 3 5 6 10 15 30}{30}=\frac{72}{ 30}=\frac{12 {5}}$$
数値 m mn がある場合、数値 n は「フレンドリー数値」と呼ばれます。
$\mathrm{\frac{\sigma(m)}{m}=\frac{\sigma(n)}{n}}$
フレンドリーペア -同じ余剰インデックスを持つ2つの数値は「フレンドリーペア」と呼ばれます。
###問題文###例 1
リーリー リーリー$$\mathrm{\frac{\sigma(140)}{140}=\frac{1 2 4 5 7 10 14 20 28 35 70 140}{140 }=\frac{336}{140}= \frac{12}{5}}$$
\frac{\sigma(30)}{30}=\frac{\sigma(140)}{140} であるため、30 と 140 はわかりやすい数字のペアです。
例 例 2
リーリー リーリー$$\mathrm{\frac{\sigma(24)}{24}=\frac{1 2 3 4 6 8 12 24}{24}=\frac{60}{ 24}=\frac{15 {6}}$$
$\mathrm{\frac{\sigma(5)}{5}\neq\frac{\sigma(24)}{24}}$ であるため、5 と 24 は友好的なペアではありません。
方法 1: ブルート フォース方法 p>
疑似コード
リーリーsumOfDivisors() 関数がループを通過するため、時間計算量 - O(n)
方法 2: 豊富さ指数の縮小形
豊かさ指数の簡略化された形式は、分子と分母の両方を最大公約数で割ることによって求められます。次に、リッチネスの縮小形が等しいかどうか、つまり分子と分母が等しいかどうかをチェックすることで、2 つの数値が友好的なペアであるかどうかをチェックします。
例: C 実装
log2n) です。
要約すると、フレンドリーペアとは、同じ存在指数、つまり数値のすべての約数の合計と数値自体の比率を持つ 2 つの自然数を指します。 2 つの数値がフレンドリ ペアであるかどうかを確認するには、上記のアプローチに従って、時間計算量 O(n) の総当たり解法と時間計算量 O(n1/2log2n) の最適化解計画を指定します。 。
以上が指定された 2 つの数値が友好的なペアであるかどうかを確認しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。