java - 欧拉计划 97

Question

我正在尝试解决 Project Euler #97 问题。我不想在网上看，因为他们直接给出了解决方案。

这是练习:

The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 2^6972593−1; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2^p−1, have been found which contain more digits.

However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 28433×2^7830457+1.

Find the last ten digits of this prime number.

所以，我尝试了这个:

public static void main(String []args){ 
        BigInteger i = new BigInteger("28433")
                          .multiply(new BigInteger(String.valueOf(Math.pow(2, 7830457)))
                          .add(new BigInteger("1")));
        
        String s = i.toString();
        System.out.println(s.substring(s.length()-10, s.length()));
     }

显然那是行不通的:

Exception in thread "main" java.lang.NumberFormatException: For input string: "Infinity"

我应该如何解决这个问题(我真的卡住了)？ (请不要给出解决方案，只是提示)

谢谢

Answer 1

你有一个问题，你想要答案 mod 10^10(最后十位数字)

使用二的幂可以更快地计算幂。例如x*x = x^2 和 x^2 * x^2 = x^4 等等。 7 830 457 = 0b11101110111101110111001 是 2^23 + 2^22 + 2^21 + 2^19 ... 2^0 所以它是 x^(2^23) * x^(2^22) * x(2^ 21) * x ^(2^19) * ... x 您必须执行每个操作 mod 10^10 以避免溢出。您可以将其乘以第一个常数并加 1。

使用这种方法，您可以在 O(log N) 中进行计算，其中 N 是次幂。

将为您完成大部分工作的关键函数是 BigInteger.modPow它旨在有效地计算大幂，但只计算数字的最低部分(基于所选的 mod)