問題タブ [number-theory]

自然数nが与えられたときに、 n 個の正の約数 ( 1 とxを含む) を持つ最小の自然数xを返す、誰もが考えることができる最も効率的なアルゴリズムは何ですか? たとえば、4 を指定すると、アルゴリズムは 6 (除数: 1,2,3,6) になります。つまり、6 は 4 つの因数を持つ最小の数です。同様に、6 を指定すると、アルゴリズムは 12 (除数: 1,2,3,4,6,12) になります。つまり、12 は 6 つの異なる因数を持つ最小の数です。

実世界のパフォーマンスに関しては、毎秒10 ⁷の計算を実行できるマシンで 2 秒以内に 10 ²⁰のオーダーの答えを出すことができるスケーラブルなアルゴリズムを探しています。

O（N）の下でこの問題を解決するためのアルゴリズムを探しています。

2つの実数aとbが与えられた場合（一般性を失うことなく、両方とも0と1の間であると見なすことができます）式を最小化する-NとNの間の整数nを見つけます。

| an --b --round（an --b）|

ユークリッドの互除法はこれにはうまくいくかもしれないと私たちは考えましたが、それを理解することはできません。整数nを徹底的に検索するよりも、これを行うにははるかに高速な方法があるはずです。

注：この状況では、aとbが頻繁に変更される可能性があるため、ルックアップテーブルのaとbを修正することは可能ですが、Nも変更される可能性があるため、少し見苦しくなります。ルックアップテーブルをまだ詳細に調べていないので、Nの関数としてルックアップテーブルをどれだけ小さくできるかを確認します。

2 つの数字がx1ありx2ます。数値については、とyの公約数をできるだけ に近づけたいと思います。x1x2y

これに効率的なアルゴリズムはありますか？

私の問題を言い換えて、より明確にする時が来たと思います。これは整数に関するものではありません...つまり、 と の 2 つの数値があるx1としx2ます。たとえば、ユーザーが数字を入力しますy。私が見つけたいのは、とが非常に小さい (たとえば、 よりも小さいが、この数値を と呼びましょう)y'に近い数値です。言い換えれば、最適なアルゴリズムは必要ありませんが、適切な近似が必要です。yx1 % y'x2 % y'0.02LIMIT

皆さんの時間と労力に感謝します。本当に親切です!

Project Euler の 10 番目の問題:

10 以下の素数の和は 2 + 3 + 5 + 7 = 17 です。

200 万未満のすべての素数の合計を求めます。

このスニペットを見つけました：

ここで公開されて おり、3 秒間実行されます。

私はこのコードを書きました：

私のコード (2 番目のコード) が非常に遅い理由がわかりません。

始める前に言っておきますが、これは宿題ではなく、単純で古くて楽しいものです。

今、私はこの質問1/x + 1/y = 1/nに答えることができるアルゴリズムを考え出そうとしています! .

上記のリンクからわかるように、著者は実際の答えではなくヒントだけを求めているので、私も同じことをお願いしたいと思います.

答えの1つが示唆するように (x - n!)(y - n!) = (n!)^2 まで式を単純化し、その時までに (x,y) ペアの組み合わせの数を理解しましたn!^2 の約数と同じです (ここで間違っていたら訂正してください)。

したがって、受け入れられた回答で示唆されているように、N!^2 を構成する各素数のすべての要素の乗算を取得しようとしています。

試行除算を使用して N!^2 を因数分解し、エラトステネスの篩を使用して sqrt(N!^2) までのすべての素数を取得するC のコードを考え出しました。

問題はメモリです。N = 15 で試してみましたが、私の Mac (Quad Core 6GB のメモリ) はほとんど死んでしまいました。問題はメモリでした。だから私はいくつかのprintfを追加し、N = 11で試しました：

リストは、N!^2 のすべての素因数です (もちろん、1 と N!^2 以外に)。

メモリ消費と可能な最適化を最小限に抑える方法についてのヒントが欲しいです。

以下のコードは簡単な実験だったので、最適化できると確信しています。

編集：

例として、初期方程式のすべての可能な正の整数解を得るための計算を示します。

3!^2 = 36 = (3^2*2^2*1^0)

したがって、ディオファントス方程式には (1+2)(1+2)(1+0)=9 の可能な正の整数解があります。負の整数を数える場合は 2 倍になります。確かにWolframAlphaを使用しています。

編集2：

「階乗とは何か」を見つけたばかりだと思います。次の非常に興味深い出力が得られます。

ありがとう

私はACM ICPCの過去の問題を練習していましたhttp://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1030

私はこの問題を解決することができず、3 秒の制限時間内に効率的に解決する方法がまったくわかりません。この問題は数論に基づいていると思いますが、どうすればよいか正確にはわかりません。ありがとう！

2011年までの合計が0を超える10個の整数を見つけますが、それらの逆数の合計は1です。

例えば

x1 + x2 + .. + x10 = 2011

1 / x1 + 1 / x2 + .. + 1 / x10 = 1

私はここでこの問題を見つけましたhttp://blog.computationalcomplexity.org/2011/12/is-this-problem-too-hard-for-hs-math.html

計算の複雑さは何で、どのタイプのアルゴリズムがそれを解決できるのか疑問に思いました。

EDIT2：私は十分に速い次のブルートフォースコードを書きました。しかし、解決策が見つからなかったので、仮定を少し調整する必要があります。私は今、私が解決策を見つけると確信しています。

この問題に対するより良いアプローチを見つける手助けが必要です (もっと数学的なアプローチかもしれません!)。詳細は次のとおりです。

問題文：

N と M を指定すると、(a+b) が M で割り切れる a,b (1 <= a < b <=N) のペアがいくつあるかを調べる必要があります。たとえば、N=4 で M=3 の場合、合計が M で割り切れる 2 つの可能なペアがあり、それらは (1,2) と (2,4) です。

制約: 1 <= N <= 10^9 および 2 <= M <= 10^9。 制限時間：1秒

私のアルゴリズムでは、N 回ループして、O(N) アルゴリズムにしています。コードは次のとおりです。

1 =< a < n の範囲 (2a,n+a) で、M で割り切れる数の数を確認しているだけです。範囲内のすべての(a,b)の合計を見ると、なぜ(2a,n+a)を取ったのかがわかります。

ただし、このO(N)アプローチはあまり高速ではありません。N=10 ⁹および M=2 の場合、プログラムは答えを 249999999500000000 として 12 秒で出力しますが、これはかなり遅いです。他にどのようなアプローチを使用できますか? より良いアプローチは考えられません。助けてください！

大学のコースでMASH-2ハッシュ関数を使用しましたが、試験では、関数電卓のみを使用してこのような（（62500）^ 257））mod（238194151）を計算するための質問に直面しました。今、私はa ^ b（mod n）を使ったいくつかの理論を知っていますが、上記の問題を手動で計算することさえ困難です。これを解決するには約15分かかると思います。これを行うためのより速い方法があるかどうか知りたいです。または、2進数でそれを行う方法がある場合でも（数値を2進数に変換してから、いくつかの操作を行います）。関数電卓を使って手作業でこれを行う必要があります。

fmod 関数を使用しようとしていますが、期待した結果が得られません。