我如何处理 Java 中的大量数字？

Question

我正在为我的竞争性编程 class 的作业编写一个程序，但我无法解决一个问题。这个问题要求你根据特定条件计算特定字符串的所有排列，而我的程序就是这样做的。然而，问题是当输入是一个非常大的字符串时，它可以达到 10^6。

问题的解决方案是2^result，其中result取决于输入字符串的长度，所以对于10^6，它可以达到5*10^5。解决方案必须以以下形式给出：result % (10^9 + 7).

我试过将解决方案放入 BigInteger 中，它用完了堆 space。我试过使用双打，它溢出了。有什么我想念的或者有办法解决这个问题吗？谢谢。

这里有一些尝试：

System.out.println((int) (Math.pow(2, counter) % (1e9 + 7)));
//it prints out 0, probably due to overflow?

DecimalFormat df = new DecimalFormat("#");
System.out.println(df.format(Math.pow(2, counter) % (1e9 + 7)));
//prints out �

Answer 1

您不需要处理非常大的数字来执行此操作。

作业旨在让您实施 modular exponentiation. BigInteger already implements it as modPow。它允许您计算 (b^e) % c 而不必处理明显大于 c.

的数字

这是维基百科关于通过重复平方求幂后的余数的伪代码：

function modular_pow(base, exponent, modulus)
    if modulus = 1 then return 0
    Assert :: (modulus - 1) * (modulus - 1) does not overflow base
    result := 1
    base := base mod modulus
    while exponent > 0
        if (exponent mod 2 == 1):
           result := (result * base) mod modulus
        exponent := exponent >> 1
        base := (base * base) mod modulus
    return result

我如何处理 Java 中的大量数字？

How can I handle enormously large numbers in Java?

java

largenumber