Login
Immutable PageDiscussionInfoAttachments
iz/競技プログラミング/Project Euler 026 Reciprocal cycles

MMA

http://projecteuler.net/problem=26

循環小数1/d(d < 1000)のうち、循環の長さが最大となるdを求める。

そもそも循環するかどうかと10^x - 1がdで割れるかどうかを見た。 ソースコード中ではcycleの仮引数nがdと対応している。

   1 #!/usr/bin/env ruby
   2 
   3 def cycle(n)
   4   # 2と5は循環の長さには影響しない
   5   n /= 2 while n % 2 == 0  
   6   n /= 5 while n % 5 == 0  
   7   # 循環の長さは'(10^x - 1) % n == 0となるxの長さ'-1と等しい
   8   i = 10
   9   loop do
  10     return 0 if i % n == 0
  11     return i.to_s.length - 1 if (i - 1) % n == 0
  12     i *= 10
  13   end
  14 end
  15 
  16 cycle_len = (1...1000).map(&method(:cycle))
  17 p cycle_len.index(cycle_len.max) + 1

iz/競技プログラミング/Project Euler 026 Reciprocal cycles (last edited 2012-12-22 10:28:17 by iz)