Problem 175

http://projecteuler.net/index.php?section=problems&id=175
前に似たような問題があった。
結論からいうとユークリッドの互除法のようなもの

import Data.List
step :: Integral a => (a,a) -> Maybe (a,(a,a))
step (p,q) | q == 0 = Nothing
           | p <= q = let (n,q') = divMod q p in Just (n,(p,q'))
           | otherwise = let (n,p') = divMod p q
                         in if p' == 0 then Just (n-1,(q,q)) else Just (n,(p',q))
                            
main = putStrLn.init.tail.show.reverse.unfoldr step $ (123456789,987654321)