問題タブ [lcm]

このコードは、N 個の数値から LCM を実行する必要があります。

どこが間違っているのかを確認するために、できる限りプリントを貼ってみました。そして私はあると思います：

しかし、私はそれを機能させることはできません。手伝っていただけませんか？

私はPerlの新人です。この問題を解決できることを願っています。
また、変数を変更しようとしましたが、機能しません。つまり

完全なコード

両方とも100000の範囲の2 つの整数nとkが与えられます。

n* ^n-1 C ₀ (n と (n-1 は 0 を選択) の乗算)、n* ^n-1 C ₁ (n と (n-1 は 1 を選択) の乗算)、 nの LCM を計算する方法* ^n-1 C ₂ (n と (n-1 は 2 を選択) の乗算), ............, n* ^n-1 C _k (n と (n-1 は k を選択) の乗算) ) モジュロ1000000007で。

私は単にすべての値を見つけて、数値が大きくなると多くの問題を抱えているモジュロを計算しています。

それを効率的に計算する方法は？

プログラムは最初に、2 つの数字を何回入力するかを入力するように求めます。2 つの数値を指定すると、それらの LCM が検出され、最初に入力した回数だけ操作が実行されます。

それは開き、私が数字を与えるのを待ち、何もしません。

}

2つの数値aとbのhcfとlcmを見つけるために、Pythonで次のプログラムを書きました。xは2つの数値のうち大きい方で、yは小さい方で、どちらもプログラムの上部で見つけようとしています。これらは後で hcf と lcm を見つけるために使用されますが、実行すると x が赤色で表示されます。理由がわかりません。

lcm、hcf を見つけるこのアルゴは C で完全に機能するため、アルゴに問題があるとは思いません。構文の問題かもしれません。

問題：見つける

nの範囲: 1<= n <=

主な課題は、大きくなる可能性のあるクエリ (Q) の処理です。1 <= Q <=

これまでに使用した方法：

強引な

複雑さ :

でのクエリの前処理と処理

最初に、すべての N のオイラー totient 関数の値を保持するテーブルを作成します。これは O(N) で実行できます。

各クエリに対して N を因数分解d*phi[d]し、結果に追加します。

これには O(sqrt(N)) が必要です。

複雑さ : O(Q*sqrt(N))

O(1) でクエリを処理する

上で説明したふるい法に、必要な答えを O(NLogN) で計算する部分を追加します。

残念ながら、これは指定された制約と制限時間 (1 秒) でタイムアウトになります。

これには、 N の素因数分解に関する巧妙なアイデアが含まれていると思います。上記で作成した lp(lowest prime) テーブルを使用して O(LogN) の数値を素因数分解できますが、因数分解を使用して答えに到達する方法がわかりません。

この問題の入力は、正の整数と単一の正の整数 k の配列 A です。プログラムの出力は、k が以下で定義されたセット S にある場合は True、そうでない場合は False です。

セット S を次のように定義します。

1. x が A にある場合、x は S にある
2. x と y が S にある場合、GCD(x,y) は S にある
3. x と y が S にある場合、LCD(x,y) は S にある

追加の制約: 配列 A のサイズは ≤ 50000、k ≤ 10 ¹²、および A の各 x について x ≤ 10 ¹²です。プログラムは 1 秒以内に答えを返さなければなりません。

いい考えがありません。私が考えることができる唯一のことは、配列内の整数の任意のペアの GCD と LCM を見つけることです。その後、集合 S を拡大できます。 .

皆さんが私を助けてくれることを願っています。私はこれに長い間立ち往生しています。

アップデート：

たとえば、配列は A= { 10, 12, 15 } です。

前述したように、S = {..., 10, 12, 15, ...}

10、12、15 は S にあることがわかっています。したがって、それらの GCD と LCM も S にあります。つまり:

S で GCD(10, 12) = 2

S で GCD(10, 15) = 5

S で GCD(12, 15) = 3

LCM(10, 12) = S で 60

...

ついに：

S = { 1, 2, 3, 5, 10, 12, 15, 30, 60 }

マイコンの音源プログラムを書いています。

ハードウェアタイマーを使用して割り込みをトリガーし、特定の音符の特定の瞬間に信号をハイまたはローに設定する必要があるかどうかを確認します。

私はかなり限られたハードウェアを使用しているので、タイマーの実行が遅いほど、他のことをしなければならない時間が長くなります (シリアル通信、生成する次のノートのロードなど)。

最適な結果を得るには、タイマーを実行する頻度を見つける必要があります。つまり、十分に正確な頻度を生成し、他のことを計算する時間があります。

これを達成するには、再生する必要があるすべての周波数のおおよその LCM を見つける必要があります (周波数が高くなるほど、人間の耳がエラーに気付くには値を不正確にする必要があるため)、再生する必要があるすべての周波数の LCM:この値は、ハードウェア タイマーを実行する頻度になります。

そのような数を計算するのに十分単純なアルゴリズムはありますか? （編集、「十分に単純」を明確にします：8ビットAVRマイクロコントローラで50未満の値に対して時間t << 1秒で実行するのに十分高速で、最悪でも数十行で実装可能です。）

以下のプログラムは 2 つの数値の LCM を計算します。予想される出力は 54 と 24 の入力で 216 ですが、57 になります。

誰かが同じことを手伝ってくれますか。以下のコード スニペットの何が問題なのか教えてください。