互除法だけど、引き算の回数を数えるのが横断的関心事なので副作用が書けないHaskellではめんどい。

divMod :: Int -> Int -> (Int, Int)
divMod n q = last . takeWhile ((>= 0) . snd) . (init :) . scanl process init
                                                                     $ repeat q
  where
    init = (0, n)
    process = flip $ \m -> (+ 1) `cross` (subtract m)

cross :: (a -> b) -> (c -> d) -> (a, c) -> (b, d)
cross f g (x, y) = (f x, g y)

countMinus :: Int -> Int -> Int
countMinus n m = snd (if n < m then countMinus' m n else countMinus' n m)
  where
    countMinus' n m
      | m == 0 = (n, 0)
      | otherwise = id `cross` (+ q) $ countMinus' m r
        where
          (q, r) = Main.divMod n $ m

こういうときにStateモナド使うといいって話は、気が向いたら書く。