指定された 2 つの数値が友好的なペアであるかどうかを確認します

フレンドリーナンバー -数理論によれば、フレンドリーナンバーとは、同じ存在指数を持つ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つの数値は「フレンドリーペア」と呼ばれます。

＃＃＃問題文＃＃＃

2 つの数値 Num1 と Num2 を与えます。 2 つの数値が友好的なペアではない場合に返します。

例 1

リーリー リーリー

説明

の中国語訳は次のとおりです:

説明

$$\mathrm{\frac{\sigma(30)}{30}=\frac{1 2 3 5 6 10 15 30}{30}=\frac{72}{ 30}=\frac{12 {5}}$$

$$\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(5)}{5}=\frac{1 5}{5}=\frac{6}{5}=\frac{6}{5}} $ $

$$\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>

この問題を解決する強引な方法は、まず 2 つの数値のすべての約数の合計を見つけ、次にそれらの存在量指数の値を計算し、比較して結果を得るというものです。

疑似コード

リーリー

例: C 実装

次のプログラムでは、すべての約数の合計を計算して、豊かさ指数を求めます。

リーリー ＃＃＃出力＃＃＃ リーリー

sumOfDivisors() 関数がループを通過するため、時間計算量 - O(n)

空間の複雑さ - O(1)

方法 2: 豊富さ指数の縮小形

豊かさ指数の簡略化された形式は、分子と分母の両方を最大公約数で割ることによって求められます。次に、リッチネスの縮小形が等しいかどうか、つまり分子と分母が等しいかどうかをチェックすることで、2 つの数値が友好的なペアであるかどうかをチェックします。

疑似コード

リーリー

例: C 実装

次のプログラムでは、分子と分母を比較することによって、2 つの数値の短縮形の存在量指数が同じであるかどうかを確認します。

リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量 - sumOfDivisors() 関数の時間計算量は O(n

1/2

log2n) です。

空間の複雑さ - O(1)

＃＃＃結論は＃＃＃

要約すると、フレンドリーペアとは、同じ存在指数、つまり数値のすべての約数の合計と数値自体の比率を持つ 2 つの自然数を指します。 2 つの数値がフレンドリ ペアであるかどうかを確認するには、上記のアプローチに従って、時間計算量 O(n) の総当たり解法と時間計算量 O(n^1/2log2n) の最適化解計画を指定します。 。

以上が指定された 2 つの数値が友好的なペアであるかどうかを確認しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。