Javaで膨大な数を扱うにはどうすればよいですか？

Question

私は競争力のあるプログラミングクラスの宿題のためのプログラムを書いています.1つの問題を乗り越えることはできません。この問題は、特定の条件に基づいて特定の文字列のすべての順列を計算する必要があり、私のプログラムはそれを行います。しかし、問題は、入力が実際に大きな文字列である場合です。最大10^6になります。

問題は2^resultです。結果は入力文字列の長さに依存するため、10^6の場合は5 * 10^5までです。解決策は、result％（10^9 + 7）の形式で指定する必要があります。

私はBigIntegerにソリューションを入れようとしましたが、ヒープスペースが不足しています。ダブルスで作業しようとしましたが、オーバーフローします。私が行方不明のものがあるのか​​、これに対処する方法がありますか？ありがとうございました。

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はすでにmodPowとして実装しています。 cよりもかなり大きな数値を処理することなく、(b^e) % cを計算することができます。

ここで残りのためのWikipediaの擬似コードが繰り返さ二乗を通じて累乗した後です：

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