ここでこの問題に遭遇しました。今年初めに開催されたプログラミングコンテストでした。
要約は次のとおりです。
N 個の整数の配列が与えられた場合、連続するすべての M 個の整数の LCM を見つけます。
例えば

出力:

実際、ここにソリューションのスケッチがありますが、動的プログラミングの部分を理解できませんでした。
したがって、誰かがいくつかの例を使用して同じソリューションについて詳しく説明できれば、それは素晴らしいことです。
新しい、わかりやすいソリューションも高く評価されます。

配列 a に n 個の整数が格納されています。たとえば、a[0]、a[1]、.....、a[n-1] で、それぞれa[i] <= 10^12とn <100. ここで、これらの n 個の整数の最小公倍数 ({a[0],a[1],.....,a[n-1]} の最小公倍数) のすべての素因数を見つける必要があります。

方法はありますが、より効率的な方法が必要です。

私の方法：

この問題に対するより良いアプローチはありますか?

問題へのリンクを投稿しています：

http://www.spoj.pl/problems/MAIN12B/

私のコードへのリンク: http://pastebin.com/R8TMYxNz

解決：

Daniel Fischer が提案したように、私のコードには、ふるいの高速化やマイナーな変更などの最適化が必要でした。これらすべての変更を行った後、問題を解決できました。これは、1.05 秒かかった SPOJ で受け入れられたコードです。

場合によっては、誰かがより良い方法またはより速い方法でそれを行うことができる場合は、私に知らせてください.

一連の整数の最小公倍数を見つけたいと思います。これを行う数値Javaライブラリは存在しますか? それへのリンクを提供してください。

タイトルが説明しているように、これは 1 から 20 までの数の lcm を見つけるためのプログラムです。これを行うアルゴリズムを見つけました
。 ウェブページには、アルゴリズムをよりよく説明する Java アプレットがあります。

問題: コード コンパイラはエラーを表示しないと書きましたが、コードを実行するとプログラムが暴走します。無限ループの可能性があると思いますが、私の人生では理解できません。私はターボC ++ 4.5を使用しているので、基本的に誰かがコードを見て助けてくれれば、それは素晴らしいことです. 前もって感謝します

アルゴリズム:

2,6,8 の lcm を見つける必要があるとします。

最初に、シリーズの最小のものを見つけ、それに上の数を追加します。つまり、シリーズは次のようになります。

4,6,8

ここで、最小値を再度見つけて、列の初期値、つまり 2 を追加します。

6,6,8

したがって、次の反復は

8,6,8

8,12,8

10,12,8

10,12,16

12,12,16

14,12,16

14,18,16

16,18,16

18,18,16

18,18,24

20,18,24

20,24,24

22,24,24

24,24,24

ご覧のとおり、ある時点ですべての数値が等しくなり、これが lcm です

私は周りを見回して、答えのある他の質問を見つけましたが、この特定の質問の範囲に対処するものはありません。

効率的な方法で広範囲の数値の LCM を計算する必要があります。他の質問は、このアルゴリズムが処理しなければならないほど大きな数値範囲を扱っていないため、あまり詳しく調べませんでした。

私が今持っているコードは、約 90 秒で 1 から 350000 までのすべての数値の LCM を計算できます。(結果の数値は、10 進数で 76000 桁の長さになります)。最終的には、数百万、場合によっては数十億の要素の長さの範囲にわたってスケーリングできるようになることを願っています。

おそらく最終的には並列化されるでしょう。一部のアルゴリズムでは、これはまったく難しくありませんが、他のアルゴリズムではよりトリッキーになります (たとえば、アルゴリズムが現在生成されている LCM を使用して、計算の他の部分の素数を計算する場合)。

ここにあります：

典型的な for ループとは異なり、この関数は [lower, upper) ではなく [lower, upper] に対して動作することに注意してください。この動作は意図的なものです。

数学をサポートするビットは、いくつかの数値セットの LCM は、プールの外部を必要とせずに任意の数値を生成できる素因数のセットの積であるということです。範囲が [1,20] の場合、次のように表すことができます。

このような広い範囲で LCM を計算するより効率的な方法はありますか?

誰かが提案するアルゴリズムが非常にメモリを大量に消費するかどうかは気にしません。この場合、時間のパフォーマンスはメモリのパフォーマンスよりもはるかに重要です (また、より高価です)。

これは宿題の質問ではありません。

質問

非常に大きな範囲の数値の最小公倍数を計算する最も効率的な方法は何ですか? このアルゴリズムは、法外に広い範囲の数値を操作する必要があるため、慎重に最適化する必要があります。

補遺1

密接に関連する質問は次のとおりです。ある BigInteger の対数を計算する最も効率的な方法は何ですか (別の BigInteger を底にします)。結果の値は、最も近い整数に切り捨てられます。

まず第一に、小さな説明です。私はこの問題で AC を取得しましたが、私のより良いアプローチ (これは数学的に同等であり、AC ソリューションと仮定します) は WA の評決を得​​ることです。

1 つの友好的な番号と N の非友好的な番号があります。友好的な数を正確に分割し、非友好的な数を分割しない数がいくつあるかを見つけたいと考えています。

入力フォーマット:

入力の最初の行には、スペースで区切られた 2 つの数値 N と K が含まれています。N は友好的でない番号の数、K は友好的な番号です。入力の 2 行目には、スペースで区切られた N 個の不適切な数字が含まれています。

出力フォーマット：

答えを 1 行で出力します。

サンプル入力:

8 16
2 5 7 4 3 8 3 18

サンプル出力:

1

説明：

指定された友好的な数 16 の約数は { 1, 2, 4, 8, 16 } であり、非友好的な数は { 2, 5, 7, 4, 3, 8, 3, 18 } です。1 はすべての友好的でない数を割り、2 は 2 を割り、4 は 4 を割り、8 は 8 を割りますが、16 はそれらのどれも割りません。したがって、友好的な数を割り、非友好的な数を割り切らない数は 1 つだけ存在します。したがって、答えは 1 です。

私のアルゴ（ACを取得した）は次のとおりです。

1. 0<=i である可能性のある不適切な数値を input[i]

2. 各input[i]について、gcd(input[i],k)を見つけます。

3. セット内の範囲 (0,n) 内のすべての i について、gcd(input[i],k) のすべての因子を格納します。このセットを、PossibleFactors と呼びましょう。

4. k の因子ごとに、PossibleFactor のいずれかの要素を除算するかどうかを確認します。「いいえ」の場合は、回答数を増やします

以下を想定してアルゴリズムを修正しました。

gcd(input[i],k) のすべての因数を set に格納する代わりに、範囲 (0,n) 内のすべての i について gcd(input[i],k) の lcm を見つけます。これは、次の LOC で簡単に実行できます。

ここで、k のすべての因数について、それらが lcm を分割するかどうかを確認します。そうでない場合は、カウントを増やします。

しかし、この仮定は私にWAを与えています。それは私の論理に欠陥があるためですか？はいの場合、2つのアプローチの違いを（可能であれば数学的な証明で）指摘してください。

参照用の2番目のアプローチを使用したコードを次に示します（およびバグの可能性があります）

大量の浮動小数点数をリストに入れ、すべての数値の最小公倍数を見つけるにはどうすればよいですか?

私の問題は、太陽系に関する情報を含むテキスト ファイルがあり、各惑星とその月の公転期間の値を分離しており、すべての期間の LCM を見つけたいと考えていることです。問題は、ピリオドがすべて整数ではなく浮動小数点数であり、それらのリストを作成できないことです。また、LCM方程式の開発に問題があります..どんな助けでも大歓迎です

ヨルダン

以前は goto だった現在のコーディングがありますが、嫌われているので、もう goto を使用しないように言われました。私はそれを for と言う while ループに変更するのに苦労しています。私はC＃とプログラミング全般にかなり慣れていないので、これのいくつかは私にとってまったく新しいものです。どんな助けでも大歓迎です。実際の問題は、2 つの数値を入力して最小公倍数を見つけることです。

goto を使用したオリジナルは次のとおりです。

問題 5: 2520 は、1 から 10 までの各数値で割り切れる最小の数値です。1 から 20 までのすべての数で割り切れる最小の正の数は?

Project Eulerの問題5を解きました

Javaコードは次のとおりです。

これをどのように最適化できますか？

アンドロイド 2.3.3

2 つ以上の数値の LCM を計算するプログラムを作成しましたが、うまくいきました。探している方の参考になればと思い、シェアさせていただきました。これは最善の解決策ではないかもしれませんが、私の要件に従って実行しました。必要に応じて変更できます。

入力をハードコーディングしました。また、プログラムは ArrayLists を使用して操作を行います。これらを変更したい場合があります。

前提条件 ::: 1. 入力範囲の PrimeNumbers の計算。

次の入力の場合 :::

次の入力の場合 :::

私はAndroidとJavaも初めてです。したがって、これが適切な解決策ではない場合でも、気にしないでください。

それが役に立てば幸い...