言語のデータ構造に適合しない大きな整数を扱う方法

Question

私はプログラミングコンテストの予備的な問題を解決しようとしています。問題の2つを計算し、いくつかの非常に大きな整数（100 ！、2^100）。

この大きな整数の威力を計算するには、速い方法が必要です。 ？

あなたは（）ところで、私はCインタフェースと実装「任意精度演算」の項を読んで、それは（POWのために助けにはならない）私に

EDITを、このためのいくつかのアルゴリズムやデータ構造をアドバイスすることはできます：私は思います累乗法による累乗法とビットシフト法が動力学的に機能しますが、このintの階乗を計算するには速い方法が必要です。ありがとう。

EDIT2：興味のある人のために。

長さNのすべてのビット列を含む最短ビット列の長さを見つけてください（私の英語は申し訳ありませんが、例を挙げます）。例えば、長さ2（00,01,10,11）のビット列をすべて含む最短ビット列長が5（11001）である。

この問題に対する私のソリューションは、2^n個+ Nだった - 1（私は2のべき乗を計算する必要があります、私はビットシフトを使用すると思います）

他の問題は、2本の長さを考えると、ありますたとえば、入力は10,2,3です。次に、2と3で10に達するようにします（たとえば、2 + 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でした。 0から2 * N/3までのyの場合、xが整数の場合、このXとYのtotalized =（x + y）の一般化置換を計算する必要があります。 /（x！* y！）である。

Answer 1

thisのようなものは、int型またはchar型の配列を使用して自分自身をロールすることができます。 [1 | 0 | 1]または['1'|'0'|'1']（101）など

Answer 2

力を計算するには、指数のバイナリ表現を使用し、乗算の回数を減らすdihotomicアルゴリズムを使用します。 データ構造整数とpowについては整数

Answer 3

の単なる配列で、exponentiation by squaring

Answer 4

あなたは（特にGnuPGが最初に私の心に入ってくる）の暗号化プログラムの実装でご覧になる場合があります。その理由は、暗号関数も非常に大きな整数（いわゆるMultiPrecision Integers - MPI）を使用するからです。これらのMPIは、最初の2バイトが整数のサイズと後者のバイトの値がどのように値を格納するかを示すように格納されます。

GPGは、オープンソースである、ちょうどそれを見て:)

Answer 5

あなたはfolowing形式で番号を保存することができます：桁数とこの数の数字の配列。これはプログラミングコンテストで大きな数字に対処する一般的な方法です。

ここには、数値と乗算の格納を提供するクラスがあります。数字の入力と出力を簡単に追加できます。

class huge { 
public: 
    int size; 
    int data[1000]; 

    friend void mul(const huge &a, int k, huge &c) { 
     c.size = a.size; 
     int r = 0; 
     for (int i = 0; i < a.size; i++) { 
      r += a.data[i] * k; 
      c.data[i] = r % 10; 
      r = r/10; 
     } 
     if (r > 0) { 
      c.size++; 
      c.data[c.size - 1] = r; 
     } 
     while (c.size > 1 && c.data[c.size - 1] == 0) 
      c.size--; 
    } 

    friend void mul(const huge &a, const huge &b, huge &c) { 
     c.size = a.size + b.size; 
     memset(c.data, 0, c.size * sizeof(c.data[0])); 
     for (int i = 0; i < a.size; i++) { 
      int r = 0; 
      for (int j = 0; j < b.size; j++) { 
       r += a.data[i] * b.data[j] + c.data[i + j]; 
       c.data[i + j] = r % 10; 
       r /= 10; 
      } 
      if (r > 0) 
       c.data[i + b.size] = r; 
     } 
     while (c.size > 1 && c.data[c.size - 1] == 0) 
      c.size--; 
    } 
}; 

Answer 6

GMPを使用してください。階乗サポートと大規模な力などが組み込まれています。とりわけ、CとC++インタフェースを備えています。非常に大きな整数を保持する型としてmpz_tが必要です。ダブルで任意の二重の乗算を行うことができます

Answer 7

基本的な数学...

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)