如何处理不适合任何语言数据结构的大整数

Question

我正在尝试解决编程竞赛的初步问题，对于其中 2 个问题，我必须计算并打印一些非常大的整数（例如 100！、2^100）。

我还需要一种快速的方法来计算这个大整数的力量。

您能为此建议我一些算法或数据结构吗

？将为电源起作用，但我还需要一种快速的方法来计算此INT的阶乘。谢谢。

Edit2：对于那些感兴趣的人；

找到最短的弦线长度，其中包含所有长n的钻头字符串（对不起，我的英语，我举例说明）。 N＆lt; = 10000，

例如，最短的位字符串长度包括所有长度2（00、01、10、11）的位字符串为5（11001）。

的解决方案是2^n + n -1。

我解决这个问题 可以达到长度N。比如输入是10,2,3，那么2和3应该达到10（比如2+2+2+2+2,2+2+3+3,3 +2+2+3，3+3+2+2 ...）。 1＆lt; = n＆lt; 2^63。我们将以 mod 1000000007 计算答案。

我的解决方案是 2x + 3y = N，因此 x = (N - 3y) / 2 。对于从 0 到 2*N / 3 的 y，如果 x 是整数，那么我应该计算这个 X 和 Y 的广义排列，total += (x+y)！ /（x！*y！）。

Answer 1

对于整数的pow，通过平方求幂

Answer 2

您可能想看看加密程序的实现（尤其是我首先想到的 GnuPG）。原因是加密函数也使用非常大的整数（所谓的多精度整数 - MPI）。这些 MPI 的存储方式是前 2 个字节说明整数的大小，后面的字节说明如何存储值。

GPG 是开源的，看看吧:)

Answer 3

使用 GMP 来处理这些。它内置了阶乘支持和大幂等。除其他外，它还具有 C 和 C++ 接口。您需要 mpz_t 作为保存非常大整数的类型。

Answer 4

要计算幂，请使用二分算法，该算法使用指数的二进制表示形式并减少乘法的结果数量。
数据结构只是一个整数数组

Answer 5

对于 C 来说，类似 this 的东西可以工作，或者使用 int 或 char 数组来滚动你自己的数组，数组中的一个点代表一个数字。
<代码>[1 | 0 | 1] 或 ['1'|'0'|'1'] 表示 101 等。

Answer 6

您可以按以下格式存储号码：该号码的位数和数字数组。这是编程竞赛中处理大数字的常见方法。

这是一个提供数字和乘法存储的类。可以添加数字的输入和输出，这很简单。

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 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)