x と y が 2 つの数値であると仮定します。この場合、y を x で割ったときに 0 の余りが返される場合、x は y の約数であると言われます。区間内で発生する最大の約数は、区間内の最大数の要素の約数です。
###問題文###例 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 実装
時間計算量 - O(n3/2)。区間内の数値ごとに、約数を見つけるために計算量 O(n1/2) のループが実行されるためです。
上記の方法は、除数が出現するたびにマップを埋める時間を短縮することでさらに最適化できます。各数値の約数を見つける代わりに、間隔の下限と上限を計算することで、間隔内の各約数の出現を知ることができます。
可能な約数のセットは 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###アルゴリズム###
maxDivisor (a, b) の処理i = 2からbの場合 If a%i == 0 回数 = b/i - a/i 1 ######他の######
次のプログラムでは、数値の約数を逆の順序で求めるのではなく、各約数について区間内での倍数の数を求めます。
この問題に対する非常に簡単な解決策を以下に示します。
したがって、次のように使用できます。
例: C 実装
次のプログラムでは、すべての偶数が約数として 2 を持つという観察を実装します。
以上が区間内の最大公約数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。