자바에서 엄청나게 많은 수를 어떻게 처리 할 수 ​​있습니까?

Question

필자는 경쟁 프로그래밍 클래스의 숙제를위한 프로그램을 작성 중이며 한 가지 문제를 해결할 수 없습니다. 이 문제는 특정 조건에 따라 특정 문자열의 모든 순열을 계산해야하며 내 프로그램에서이를 수행해야합니다. 그러나 문제는 입력이 매우 큰 문자열 인 경우 최대 10^6까지 가능합니다.

문제는 2^결과입니다. 결과는 입력 문자열의 길이에 따라 달라 지므로 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을 계산할 수 있습니다. https://docs.oracle.com/javase/8/docs/api/java

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