最大公約フィボナッチ数(?) O((logn)2)

問題：https://codeiq.jp/ace/nabetani_takenori/q649
解説：http://nabetani.hatenablog.com/entry/codeiq_gcfibo_q649

RubyによるO((logn)2)の実装例です。
とりあえず、nlognから(logn)2に縮められたことは収穫でした。
gcfibo()の最適化はしていません。3つ以上の数のgcfiboを求めたいときに使えなくなってしまうので。

ところで。

オーダー	Ruby 1.8.7	Ruby 2.0.0
O(nlogn)	0.59s	0.38s
O((logn)2)	0.01s	0.06s

Ruby 1.8の方が速い場合ってあるんですね。。

codeiq649.rb

#!/usr/bin/ruby
class Fixnum
    def fibo
        return to_enum(:fibo) if !block_given?
        yield 1
        a=1
        b=self
        loop{
            yield b
            a,b=b,a+b
        }
    end
    def dfibo
        h={}
        if false #O(nlogn)
            1.step(self-1){|i|
                a=i.fibo.take_while{|e|e<=self}
                if a.last==self
                    a.each{|e|h[e]=1}
                end
            }
        else #O((logn)2)
            1.fibo.take_while{|e|e<self}.each_cons(2){|e,f|
                if (self-e)%f==0
                    ((self-e)/f).fibo.take_while{|g|g<=self}.each{|g|h[g]=1}
                end
            }
        end
        return h.keys.sort
    end
end
DATA.each{|e|
    a=e.split.map(&:to_i)
    puts "GCFibo( #{a.join(', ')} ) = "+a.map(&:dfibo).reduce(:&).last.to_s
}
__END__
10 14
18 14
73 97
23 25
308 320
6168 9877
18518 19942

追伸
1を特別扱いしていませんが、それでもdfiboは一応求められる模様。