2

私は競争力のあるプログラミングを始めましたが、ほとんどの場合、数値の入力サイズは次のようになります

     1 <= n <=  10^(500).

したがって、単純なintメモリに格納できない500桁のようなものになることを理解しています。私は c と c++ を知っています。

配列を使用する必要があると思います。しかし、どうやって見つけるのか混乱します

   if ( (nCr % P) == 0 )  //for all (0<=r<=n)//

それを配列に格納してからnCrを見つけると思います。これには、数字の乗算と除算をコーディングする必要がありますが、モジュラスはどうですか。

他に方法はありますか？

ありがとう。

4

4 に答える 4

3

乗算と除算を自分でコーディングしたくないと思いますが、GNUMPBignumライブラリhttp://gmplib.org/のようなものを使用してください。

于 2012-09-06T06:19:29.567 に答える
1

多数のライブラリに関して、私はttmathを使用しました。これは、任意の長さの整数、浮動小数点数などを提供し、いくつかの非常に優れた操作をすべて比較的少量で提供します。

ただし、(n^e) mod m が何であるかを理解しようとしているだけの場合は、非常に大きな数の計算をしなくても、e の非常に大きな値に対してこれを行うことができます。以下は、それを行うためにローカルの ttmath ライブラリに追加した関数です。

/*!
        mod power this = (this ^ pow) % m
        binary algorithm (r-to-l)

        return values:
        0 - ok
        1 - carry
        2 - incorrect argument (0^0)
    */
    uint PowMod(UInt<value_size> pow, UInt<value_size> mod)
    {
        if(pow.IsZero() && IsZero())
        // we don't define zero^zero
        return 2;

        UInt<value_size> remainder;
        UInt<value_size> x = 1;

        uint c = 0;

        while (pow != 0)
        {
            remainder = (pow & 1 == 1);
            pow /= 2;
            if (remainder != 0)
            {
                c += x.Mul(*this);
                x = x % mod;                                
            }

            c += Mul(*this);
            *this = *this % mod;        
        }

        *this = x;
        return (c==0)? 0 : 1;
    }

このアルゴリズムでは、n^2 より大きい数値を格納する必要はないと思います。これらのヘッダーを使用したくない場合は、ttmath 関連の側面を削除するように簡単に変更できるはずです。

気になる場合は、べき乗剰余を調べることで、数学の詳細をオンラインで見つけることができます。

于 2012-09-06T06:30:15.667 に答える
0

多くの中。これらのコーディング コンテストの多くの場合、これらの大きな数字を実際に計算するのではなく、計算せずに質問に答える方法を見つけようという考え方です。例えば：

What are the last ten digits of 1,000,000! (factorial)?

500万桁を超える数字です。しかし、その質問には、コンピューターがなくても、ペンと紙がなくても答えられます。または、次の質問に答えてください: (2014^2014) modulo 153 とは? Cでこれを計算する簡単な方法は次のとおりです。

int modulo = 1;
for (int i = 0; i < 2014; ++i) modulo = (modulo * 2014) % 153;

繰り返しますが、6,000 桁の数字で計算を行うことを避けました。（実際にはこれをかなり速く行うことができますが、私は競争に参加しようとはしていません）.

于 2014-05-31T09:29:56.683 に答える