区間内の最大公約数

x と y が 2 つの数値であると仮定します。この場合、y を x で割ったときに 0 の余りが返される場合、x は y の約数であると言われます。区間内で発生する最大の約数は、区間内の最大数の要素の約数です。

＃＃＃問題文＃＃＃

間隔 [a, b] を指定します。 a と b (「1」以外) を含む範囲で現れる最大の約数を求めます。すべての約数が同じ回数出現する場合は 1 を返します。

例 1

リーリー リーリー

説明

- 2 の約数 = {1, 2}、3 の約数 = {1, 3}、4 の約数 = {1, 2, 4}、5 の約数 = {1, 5}。 2 は最頻約数です。 例 2

リーリー リーリー

説明

- 2 の約数 = {1, 2}、3 の約数 = {1, 3}、4 の約数 = {1, 2, 4}、5 の約数 = {1, 5}。 2 は最頻約数です。 方法 1: ブルート フォース クラッキング

この問題を解決する強引な方法は、区間内のすべての数値のすべての約数を見つけて、それらを出現回数とともにマップに保存することです。

＃＃＃アルゴリズム＃＃＃

プロセス除数(数値)

i = 1 ～ n1/2 の場合 1

• If num%i == 0

• If num/i == i

• i がマップにない場合は、(i, 1)

を挿入します

• そうでない場合はマッピング[i]

＃＃＃＃＃＃他の＃＃＃＃＃＃

• i がマップにない場合は、(i, 1)

を挿入します

• そうでない場合はマッピング[i]

• num/i がマップにない場合は、(num/i, 1)

を挿入します。

• その他のマップ[num/i]

• maxDivisors (a, b) の処理

• n = a ～ bの場合

除数 (n)

• map.erase(1)

• 除数 = 1、カウント = int_min

• マップ内の各要素について

• if it.value > count

• カウント = it.value

• 除数 = it.key

• 例: C 実装

次のプログラムでは、divisors() 関数で各数値の約数を求め、maxdivisor() 関数で最大の約数を求めます。
• リーリー ＃＃＃出力＃＃＃ リーリー

  時間計算量 - O(n3/2)。区間内の数値ごとに、約数を見つけるために計算量 O(n1/2) のループが実行されるためです。

空間の複雑さ - O(n)、マップ空間。

方法 2

上記の方法は、除数が出現するたびにマップを埋める時間を短縮することでさらに最適化できます。各数値の約数を見つける代わりに、間隔の下限と上限を計算することで、間隔内の各約数の出現を知ることができます。

間隔 [2, 5] を例として考えてみましょう。

可能な約数のセットは 1 ～ 5 です。したがって、1 = 5/1 - 2/1 1 = 4 が発生します。 2 = 5/2 - 2/2 1 = 2 のようです。 3 = 5/3 - 2/3 = 1 のようです。 4 = 5/4 - 2/4 = 1 のようです。 5 = 5/5 - 2/5 = 1 のようです。

上記は次のように形式化できます。

下限%除数 == 0の場合、occ = 上限/除数 - 下限/除数 1

その他 occ = 上限/除数 - 下限/除数

＃＃＃アルゴリズム＃＃＃

maxDivisor (a, b) の処理

i = 2からbの場合

If a%i == 0

回数 = b/i - a/i 1

＃＃＃＃＃＃他の＃＃＃＃＃＃

• 回数 = b/i - a/i

• map.insert(i, 回)

• 除数 = 1、カウント = int_min

• マップ内の各要素について

• if it.value > count

• カウント = it.value

• 除数 = it.key

• 例: C 実装
  次のプログラムでは、数値の約数を逆の順序で求めるのではなく、各約数について区間内での倍数の数を求めます。
リーリー ＃＃＃出力＃＃＃ リーリー
• 方法 3
  この問題に対する非常に簡単な解決策を以下に示します。
• サイズが 1 より大きい区間では、数値の半分 (すべての偶数) が約数として 2 を持ちます。
  したがって、次のように使用できます。
＃＃＃アルゴリズム＃＃＃
• maxDivisors (a, b) の処理

if a == b

ans = a

＃＃＃＃＃＃他の＃＃＃＃＃＃

ans = 2

例: C 実装

次のプログラムでは、すべての偶数が約数として 2 を持つという観察を実装します。

リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃結論は＃＃＃

つまり、区間内の最大の約数を見つけるには、上記の方法を使用できます。時間範囲は O(n3/2) から O(1) で、空間範囲は O(n ) から O(1).

以上が区間内の最大公約数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。