-- f s + g t = gcd(f, g) なる (s, t) を求める
eea :: Integer -> Integer -> (Integer, Integer)
eea f g = loop f g 1 0 0 1
  where
    loop :: Integer -> Integer -> Integer -> Integer -> Integer -> Integer
         -> (Integer, Integer)
    loop r r' s s' t t' -- r = r_i-1, r' = r_i
      | r'' == 0  = (s', t')
      | otherwise = loop r' r'' s' s'' t' t''
      where
        (q', r'') = r `divMod` r' -- = (q_i, r_i+1)
        s''       = s - s' * q'   -- = s_i+1
        t''       = t - t' * q'   -- = t_i+1


-- 途中経過も表示 [(r, s, t)]
eeaList :: Integer -> Integer -> [(Integer, Integer, Integer)]
eeaList f g = loop f g 1 0 0 1
  where
    loop :: Integer -> Integer -> Integer -> Integer -> Integer -> Integer
         -> [(Integer, Integer, Integer)]
    loop r r' s s' t t' -- r = r_i-1, r' = r_i
      | r'' == 0  = [(r, s, t), (r', s', t')]
      | otherwise = [(r, s, t)] ++ loop r' r'' s' s'' t' t''
      where
        (q', r'') = r `divMod` r' -- = (q_i, r_i+1)
        s'' = s - s' * q' -- = s_i+1
        t'' = t - t' * q' -- = t_i+1


-- (s, t, gcd(f, g))
eeaGcd :: Integer -> Integer -> (Integer, Integer, Integer)
eeaGcd f g = loop f g 1 0 0 1
  where
    loop :: Integer -> Integer -> Integer -> Integer -> Integer -> Integer
         -> (Integer, Integer, Integer)
    loop r r' s s' t t' -- r = r_i-1, r' = r_i
      | r'' == 0  = (s', t', r')
      | otherwise = loop r' r'' s' s'' t' t''
      where
        (q', r'') = r `divMod` r' -- = (q_i, r_i+1)
        s'' = s - s' * q' -- = s_i+1
        t'' = t - t' * q' -- = t_i+1


-- 余りの絶対値が小さくなるような割り算
-- 9 = 2 * 5 + (-1)
absDivMod :: Integer -> Integer -> (Integer, Integer)
absDivMod a b = loop a b x
  where
    x | a * b >= 0 = 1
      | otherwise  = (-1)
    loop :: Integer -> Integer -> Integer -> (Integer, Integer)
    loop s t q
      | abs r > (abs t) `div` 2 = loop r t x
      | otherwise   = (q, r)
      where
        r = abs s - abs t
        x
          | q >= 0    = q + 1
          | otherwise = q - 1


tupleMap3 :: (a -> a) -> (a, a, a) -> (a, a, a)
tupleMap3 f (x, y ,z) = (f x, f y, f z)


absEeaList :: Integer -> Integer -> [(Integer, Integer, Integer)]
absEeaList f g = loop f g 1 0 0 1
  where
    loop :: Integer -> Integer -> Integer -> Integer -> Integer -> Integer
         -> [(Integer, Integer, Integer)]
    loop r0 r1 s0 s1 t0 t1 -- r = r_i-1, r' = r_i
      | r2 == 0   = [(r0, s0, t0), (r', s', t')]
      | otherwise = [(r0, s0, t0)] ++ loop r1 r2 s1 s2 t1 t2
      where
        (q, r2) = r0 `absDivMod` r1 -- = (q_i, r_i+1)
        s2 = s0 - s1 * q -- = s_i+1
        t2 = t0 - t1 * q -- = t_i+1
        (r', s', t')
          | r1 < 0    = tupleMap3 (*(-1)) (r1, s1, t1)
          | otherwise = (r1, s1, t1)