项目欧拉97

我想解决项目欧拉＃97问题。我不想在网上看，因为他们直接提供解决方案。项目欧拉97

这里的练习：

第一个已知的主要发现，超过一万位在1999年被发现，是形式2^6972593-1的梅森素数;它包含正好2,098,960位数字。随后发现其他Mersenne 质数为2^p-1的形式，其中包含更多数字。

然而，在2004年发现了一个巨大的非梅森素数包含2,357,207个数字：28433×2^7830457 + 1。

查找此素数的最后十位数字。

所以，我尝试这样做：

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"

我应该如何解决这个问题（我真的卡住）？（请不要给予解决，只是暗示）

感谢

来源

2013-12-18 user2336315

代替'Math.pow'使用'BigInteger'的POW方法缺失的一个因素。 –

而不是Math.pow或BigInteger.pow，使用BigInteger.powMod。或者只需使用mod。 –

@PeterLawrey什么是'BigInteger.powMod'？ –

你有你想要的答案国防部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）

来源

2013-12-18 20:11:04

谢谢，解决+1问题=） – user2336315

的问题是在计算2^7830457

他们想要的最后10位数字所以这意味着根据本数模百亿

：http://en.wikipedia.org/wiki/Modulo_operation

AB模N递归乘法将：=（（一个模N）*（B模N））模N

这样你就可以在一个循环中，你采取模量各倍增

编辑后使用乘法计算2^7830457更快

public static long pow1(int a,long b,long n){ if (b==1)return a%n; if (b%2==1){ return (pow1(a,(b-1)/2,n)*a)%n; } else{ return (pow1(a,b/2,n))%n; } }

来源

2013-12-18 20:21:10 MIE

存在递归码

def pow1(a,b,n): 
    if (b==1): 
     return a%n 
    if (b%2==1): 
     return (pow1(a,(b-1)//2,n)*pow1(a,b//2,n)*a)%n 
    else: 
     return (pow1(a,b//2,n)*pow1(a,b//2,n))%n

来源

2017-04-19 12:59:15 Ana

回答

相关问题