2

私は大きな数のために以下の式を計算しようとしています。

N!/((N/2)!(N/2)!)

この式の値は非常に大きくなるため、この式のモジュラスの値が素数である必要があります。この式の値が でxあり、素数 を選択するとします1000000007。を探していx % 1000000007ます。

これが私のコードです。

#include<iostream>
#define MOD 1000000007
using namespace std;
int main()
{
    unsigned long long A[1001];
    A[2]=2;
    for(int i=4;i<=1000;i+=2)
    {
        A[i]=((4*A[i-2])/i)%MOD;
        A[i]=(A[i]*(i-1))%MOD;

    while(1)
    {
        int N;
        cin>>N;
        cout<<A[N];
    }
}

しかし、これだけの最適化でも N の値が大きい場合は失敗します。たとえば、N が 50 の場合、正しい出力は です605552882が、これは になります132924730。正しい出力を得るためにさらに最適化するにはどうすればよいですか?

注：私はNを偶数と考えています。

4

2 に答える 2

6

剰余演算を行う場合、除算などの演算はありません。代わりに、分母のモジュラ逆数を取り、乗算します。剰余逆数は、1779 年に Etienne Bezout によって発見された拡張ユークリッド アルゴリズムを使用して計算されます。

# return y such that x * y == 1 (mod m)
function inverse(x, m)
    a, b, u := 0, m, 1
    while x > 0
        q, r := divide(b, x)
        x, a, b, u := b % x, u, x, a - q * u
    if b == 1 return a % m
    error "must be coprime"

このdivide関数は、商と剰余の両方を返します。上記の代入演算子はすべて同時代入です。最初にすべての右辺が計算され、次にすべての左辺が同時に代入されます。剰余算術の詳細については、私のブログを参照してください。

于 2013-02-06T19:13:28.157 に答える
1

  1. まず、モジュロ除算はまったく必要ありません。式は次のように書き直すことができます。

    N!/((N/2)!^2) =(1.2.3...N)/((1.2.3...N/2)*(1.2.3...N/2)) = ((N/2+1)...N)/(1.2.3...N/2))

    • わかりました今、あなたは大きい数を小さい方で割っています
    • したがって、除数と除数を掛けることで結果を反復できます
    • したがって、ブースサブの結果は同様の大きさになります
    • 両方の数値が割り切れる場合はいつでも 2 左にシフト
    • これにより、オーバーフローしないことが保証されます
    • あなたが（N / 2）のとにいるなら！残りのためにのみ乗算を続行するよりも。
    • 両方の部分結果が割り切れる場合はいつでも
    • 1で割るまで
    • この後、正常に終了するまでモジュロ演算で乗算できます。

  2. より高度なアプローチについては、これを参照してください。

    • ん！と (N/2)! 一見したよりもはるかに分解可能である
    • 私はしばらくの間それを解決しました、...
    • ここに私が見つけたものがあります：高速正確bigint階乗
    • あなたの言葉でN！そして ((N/2)!)^2 は完全に消えます。
    • 単純な素数分解 + 4N <-> 1N 修正のみが思い出させます

解決：

I. (4N!)=((2N!)^2) . mul(i=all primes<=4N) of [i^sum(j=1,2,3,4,5,...4N>=i^j) of [(4N/(i^j))%2]]
II. (4N)!/((4N/2)!^2) = (4N)!/((2N)!^2)
----------------------------------------
I.=II. (4N)!/((2N)!^2)=mul(i=all primes<=4N) of [i^sum(j=1,2,3,4,5,...4N>=i^j) of [(4N/(i^j))%2]]
  • 唯一のことは、N は 4 で割り切れる必要があるということです...したがって、すべての用語で 4N です。
  • N%4!=0 を持っている場合は、NN%4 を解くよりも、結果が misin 1-3 の数値で正しい場合。

それが役に立てば幸い

于 2013-09-03T14:31:39.923 に答える