項目歐拉97

Question

我想解決項目歐拉＃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" 

我應該如何解決這個問題（我真的卡住）？ （請不要給予解決，只是暗示）

感謝

Answer 1

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

Answer 2

的問題是在計算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; 
     } 
    } 

Answer 3

存在遞歸碼

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