問題タブ [lcm]

私はオンライン裁判官の問題を解決しようとしています: http://opc.iarcs.org.in/index.php/problems/LEAFEAT

要するに問題：

整数 L と N 個の整数 s1、s2、s3..sN のセットが与えられた場合、0 から L-1 までの si のいずれでも割り切れない数がいくつあるかを見つけなければなりません。

たとえば、与えられた場合、 L = 203、2、5S = {3,2,5}で割り切れない 0 から 19 までの 6 つの数字があるとします。

L <= 1000000000 および N <= 20。

この問題を解決するために、包含と除外の原則を使用しました。

これがこの問題を解決するための私のコードです

はnext_subset(n)、配列内にサイズ n の次のサブセットを生成します。サブセットがない場合は 0 を返し、それ以外の場合は 1 を返します。これは、このスタックオーバーフローの質問Aで受け入れられた回答で説明されているアルゴリズムに基づいています。

このlcm(a,b)関数は、a と b の lcm を返します。このget_lcm(n)関数は、 内のすべての要素の lcm を返しますA。プロパティを使用します：LCM(a,b,c) = LCM(LCM(a,b),c)

ジャッジに問題を提出すると、「制限時間超過」と表示されます。これをブルート フォースで解決すると、50% のマークしか得られません。

最大 2^20 のサブセットが存在する可能性があるため、私のアルゴリズムは遅くなる可能性があるため、この問題を解決するにはより良いアルゴリズムが必要です。

編集：

コードを編集して関数をユークリッド アルゴリズムに変更した後、間違った答えが得られますが、コードは制限時間内に実行されます。サンプル テストに対する正しい答えが得られますが、他のテスト ケースに対する正しい答えは得られません。コードを実行したideoneへのリンクを次に示します。最初の出力は正しいですが、2 番目の出力は正しくありません。

この問題に対する私のアプローチは正しいですか? もしそうなら、私は自分のコードで間違いを犯しており、それを見つけます。そうでなければ、誰かが何が間違っているのか説明してもらえますか?

次の解を見つけるためのコードの書き方: (N+1)*X =LCM( 1,2,3,4,5,6,......,N,N+1) mod を使用する場合(10^9 +7) よりも大きくなります。MOD=(10^9 +7) を使用します。次のコードフラグメントを作成しましたが、機能しません。

こんにちは、バイナリ配列を考えてみましょう:

この配列のすべての奇数行の lcm を x = 3 の 2x まで取りたいと考えています。つまり、1 番目、3 番目、5 番目の行の lcm を取得する必要があります。

しかし、両方が異なる可能性があるため、 ny x と A に適用できる汎用コードが必要です。(A と xi が何を与えても、2x までの A の奇数行の lcm を取得する必要があります。

一連の数値の最小公約数を見つける必要があります (最大 100 000 の数値で、それぞれが [0, 2 000 000 000] の範囲にあります)

次のアルゴリズムを使用しています lcm(a,b) = (a/gcd(a,b)) * b

2 つ以上の数値 lcm(a, lcm(b,c))... の lcm を見つける標準的な方法は、小さな入力値に対して機能します。

ただし、大きな入力の場合、 long long int を使用してもオーバーフローエラーが発生し始めます...

多くの大きな整数値でオーバーフロー エラーが発生しないようにするにはどうすればよいですか?

お手伝いありがとう

このプログラムでは、Scanner クラスを使用して 2 つの数値を入力として受け取り、それら 2 つの数値の最小公倍数を計算します。lcm メソッドが何も返さないことを除いて、すべてが機能しているようです。「break」ステートメントで何かを台無しにした可能性がありますが、while ループにネストされた if ステートメントから抜け出す他の方法を知りませんでした。もう 1 つの質問: while(True) ループの使用は良い方法ですか、それとも悪い方法ですか? 私はそれについて多くの複雑な意見を見たからです。while(True) ループに代わるより良い方法があれば、喜んでお聞きします。ありがとうございました！

1 から 20 までのすべての数字の lcm を見つける必要があり、このコードを思いつきました。効率は悪いですが、正解よりも2倍多い答えが出てきます。誰か教えてくれませんか？