どのようにしてNを計算することができますか？

C（C）またはC++でコンピュータ（N choose K）％Mをオーバーフローさせずにどうすればいいですか？ N（4 < = N < = 1000）とK（1 < = K < = N）とM = 1000003特定の場合についてどのようにしてNを計算することができますか？

。

出典

2011-01-09 Quixotic

[既に他の場所に回答されているようです] （http://online-judge.uva.es/board/viewtopic.php?f=22&t=42690） –

％Mを計算するには、ノミネータ（n！）モジュラスMと分母（k！*（n - k）！）モジュラスMを別々に計算し、次にそのノミネータに分母モジュラ乗法逆（M単位）。 Mは素数であるため、Fermatのリトル定理を使用して、乗法逆数を計算することができます。

次のリンク（問題SuperSum）上のサンプルコードでの素敵な説明、あります：

http://www.topcoder.com/wiki/display/tc/SRM+467

出典

2011-01-09 13:46:05 Piva

余分な速度については、分子を（K + 1）からNまでの積として計算します、分母をKとする。私たちは、素数でNよりも大きいので、計算にMの要素がないことを知っています。したがって、取り消しているものがMの倍数（つまり0）になることを心配することなく、上と下を取り消すことができます。 –

正確に私は同じことから学んだ。 – Quixotic

しかし今、私は1,000,000,003が素数ではないことを知っています。これを今解決する方法はありますか？ – Quixotic

あなたが与えたリンクから再帰式を使用し、二項係数を計算するMOD M.

出典

2011-01-09 12:08:03 Henrik

-1

使用Stirling's approximation計算を行うことができます。その後、普通のようにモジュラスを計算するだけです。

(A * B * C) % N ... is equal to... ((A % N) * (B % N) * (C % N)) % N;

、あなたはできるだけ早くそれは大きな数になると、すべてのオペランドおよび製品への弾性係数を適用する必要がある、またはすべてである：ここでは

出典

2011-01-09 12:08:34

近似は、Mを法とする二項係数をどのように計算するのに役立ちますか？近似はモジュロ演算では意味がありません。 –

申し訳ありませんが近似部分を見逃しました。 – Quixotic

は簡単な例です。最後に、モジュラスは全体の結果に適用されなければなりません。

出典

2011-01-09 12:29:22 Nawaz

32ビットintでは、1000000000 * 1000でオーバーフローが発生する可能性があります。 – ybungalobill

@ ybungalobill： '（（1000000000％N）*（1000）％N）％N'を適用します。 – Nawaz

モジュラスはNではなく問題のMであり、与えられた例は実際にはプライムではないが約10億であることに注意してください。したがって、「1000000000％N」はまだ「1000000000」です。オーバーフローを避けるには、N^2と同じ大きさの整数型が必要です（例えば、long longやint64_tなど） –

以来十億三= 23 * 307 * 141623あなたが計算することができます（nはchosesがK）のmod 23は、、307と141623を適用し、中国のリマインダー定理を適用する[1]。 n！、k！（n-k）!,オーバーフローを防ぐために、各ステップのすべてのmod 23,307および141623を計算する必要があります。

このようにして、32ビットマシンでもオーバーフローを回避する必要があります。

mod nを141623と7061（23 * 307）と計算することが少し改善されます（ただし、逆弾性率7061を計算するのは少し難しいかもしれないので、これはしません）

貧しい私の英語は申し訳ありません。

[1] http://en.wikipedia.org/wiki/Chinese_remainder_theorem

EDIT2：Nを計算するときに私が見つけたもう一つの潜在的な問題があります！ mod 23（例えば）それはおそらく0になりますが、（nがkを選んだ）ことは0のmod 23であることを意味しないので、23がnを分けた回数を数える必要があります！、（n-k）！そしてk！計算する（nはkを選択する）。これを計算するのは簡単です、pはnを割ります！正確に床（n/p）+床（n /p²）+ ...時間。それが起これば、nは23を分ける！それはkを分ける同じ時間！あなたは毎回それの乗数ごとに23で割る（nを選ぶ）mod 23を計算します。307は同じですが、141623には適用されません。

出典

2011-01-09 14:51:17

小さな素数23と307については、力を数える代わりにhttp://en.wikipedia.org/wiki/Lucas%27_theoremを使うことができます。 –

どのようにしてNを計算することができますか？

答えて

関連する問題