14

私はプログラミングコンテストの予備問題を解決しようとしています.2つの問題では、非常に大きな整数(100!、2^100など)を計算して出力する必要があります。

また、この大きな整数の累乗を計算する高速な方法も必要です。

これについていくつかのアルゴリズムまたはデータ構造についてアドバイスしてもらえますか?

編集:二乗法とビットシフトによるべき乗は電力に対して機能すると思いますが、この int の階乗を計算する高速な方法も必要です。ありがとう。

EDIT2：興味のある方へ。

長さ N のすべてのビット文字列を含む最短のビット文字列の長さを見つけます (英語で申し訳ありませんが、例を挙げます)。N <= 10000

たとえば、長さ 2(00、01、10、11) のビット列をすべて含む最短のビット列長は 5(11001) です。

この問題に対する私の解決策は 2^n + n - 1 でした (したがって、2 の累乗を計算する必要があります。ビットシフトを使用すると思います)。

もう 1 つの問題は、2 つの長さが与えられた場合に、長さ N に到達する方法の数を見つけることです。 2+2+2+2、2+2+3+3、3+2+2+3、3+3+2+2...)。1 <= N < 2^63。mod 1000000007 で anwser を計算します。

私の解決策は、 2x + 3y = N なので、 x = (N - 3y) / 2 でした。y が 0 から 2*N / 3 の場合、x が整数の場合、この X と Y の一般化順列を合計 += (x+y) で計算する必要があります。/ (x!*y!)。

4

7 に答える 7

6

pow整数の場合、二乗による累乗

于 2011-04-04T21:08:45.287 に答える
1

これらを処理するには、 GMPを使用します。階乗のサポートや大べき乗などが組み込まれています。とりわけ、C および C++ インターフェイスがあります。mpz_t非常に大きな整数を保持する型として必要になります。

于 2011-04-05T07:56:03.147 に答える
1

累乗を計算するには、指数のバイナリ表現を使用し、乗算の結果の数を減らす二分法アルゴリズムを使用します。データ構造は単なる整数の配列です

于 2011-04-04T21:06:47.780 に答える
1

暗号化プログラムの実装を調べてみるとよいでしょう (特に GnuPG が最初に頭に浮かびます)。その理由は、暗号関数も非常に大きな整数 (いわゆる MultiPrecision Integers - MPI) を使用するためです。これらの MPI は、最初の 2 バイトが整数のサイズを示し、後のバイトが値を格納する方法を示すような方法で格納されます。

GPG はオープンソースです。ぜひご覧ください :)

于 2011-04-04T21:36:46.100 に答える
0

Cの場合、このようなものが機能するか、intまたはchar配列を使用して独自の配列をロールし、配列内のスポットが数字を表します。 [1 | 0 | 1]または['1'|'0'|'1']101など。

于 2011-04-04T21:04:34.067 に答える
0

基本的な数学は、任意の double と double の乗算を行うことができます...

def biginteger(num1, num2):
result = []
lnum1 = len(num1)
lnum2 = len(num2)

k = x = remainder = 0
while len(result) < lnum1:
    result.append(0)
for i in range(lnum1, 0, -1):
    multiplier = int(num1[i - 1])
    for j in range(lnum2, 0, -1):
        temp = (int(num2[j - 1]) * multiplier) + remainder + int(result[k])
        result[k] = str(temp % 10)
        remainder = temp / 10
        k += 1
    result.append(str(remainder))
    if remainder != 0:
        remainder = 0
    x += 1
    k = x

return ''.join([result[i - 1] for i in range(len(result), 0, -1)])

num1 = '37234234234234'
num2 = '43234234234232'
print biginteger(num1, num2)
于 2012-04-06T18:31:51.513 に答える