Ruby中的項目Euler＃168;有沒有人得到答案？

-2

Project Euler problem #168。我的解決方案是：Ruby中的項目Euler＃168;有沒有人得到答案？

num = (10..10**10).inject(0) do |sum,x| 
x.to_s.chars.rotate(-1).join.to_i % x == 0 ? sum += x : sum += 0 
end 
puts num.to_s[-5..-1].to_i

我正在處理的問題是，我不知道是如果這個'解決方案'是對還是錯。當我嘗試在終端上運行時，我不會收到錯誤消息或答案。它看起來好像答案正在加載，但沒有答案出現。

我會認爲這是因爲該數組是如此之大，所以我怎麼才能找到答案的另一種方式？我知道代碼沒有錯誤，因爲我嘗試了一個更小的範圍，比如10..10 ** 6，它工作正常。

來源

2015-09-14 Jorge Lopez Jr

這不能用蠻力來解決.10^100太大了。像大多數歐拉項目問題一樣，有一些「聰明的數學屬性」必須被利用。 – user2864740

那麼有沒有其他方法可以找出問題？我只想知道答案lol –

@JorgeLopezJr：我建議你在網絡上圍繞Google進行解釋。歐拉項目是一項挑戰，你應該投入你的努力 - 無論是解決問題還是研究已知的問題。堆棧溢出社區可能在簡單/幸運的情況下給你一個答案，但這不是一個保證。 – Nayuki

數量有此權限旋轉特性的形式爲：

ABCD and DABC = k*ABCD

我們可以很容易地看到，k應小於10，因爲，如果k大於10，k*ABCD將有超過位數ABCD。

對於來自1的k每一個數目9，並與最顯著數字（MSD）是a，a from k to 9，我們可以發現，滿足X/k是X左側旋轉的最小數量X，並且X有MSD是a。

僞代碼：

for(int k = 1; k < 10; k++){ 
    for(int a = k ; a < 10; a++){ 
     long X = 0; 
     int cur = a; 
     int mod = 0; 
     do{ 
      X = X*10 + cur; 
      cur = (mod*10 + cur)/k; //Result of this division is the next digit of X 
      mod = (mod*10 + cur)%k; 
      if(pair <cur, mod> seen before) 
      break;   
     }while(cur != a && mod != 0); 
     //Notice that we will iterate less than 100 steps, as there is only 10*10 value of pair (cur, mod). 
    } 
}

我們注意到，所有的編號Y < 10^100，Y/k是Y左側轉動將有形式XXXXXX...

所以，工作是現在簡單，因爲每個Y將以X結尾，只需保留X的最後5位數字並乘以有效的Y數字（= 100/X的數字位數）即可。

總結所有這5位數字，我們將得到這個問題的答案。

來源

2015-09-14 10:39:44

Ruby中的項目Euler＃168;有沒有人得到答案？

回答

相關問題