2026-11-11
Crt.hs
crt :: (Int, Int) -> (Int, Int) -> Int
crt (a, m) (b, n) = a + m * ((b - a) * inv `rem` n)
where
inv = until (\k -> m * k `mod` n == 1) (+ 1) 1
main :: IO ()
main = print (crt (2, 3) (1, 5))
crt (a, m) (b, n) は、m で割ると a 余り、n で割ると b 余る整数のうち、0 以上 m * n 未満のものを返す関数です。m と n は1より大きく、1以外の公約数を持たず、0 ≤ a < m、0 ≤ b < n とします。crt (2, 3) (1, 5) は本来 11 を返すはずが、いまは -4 を返します。
Answer
Wrong
crt (a, m) (b, n) = a + m * ((b - a) * inv `rem` n)
m で割ると a 余る数は a + m t と書けるので、このコードは n で割った余りが b になる t を求めています。inv は m k を n で割ると1余る k で、3 と 5 なら 2 です。t は (b − a) × inv を n で割った余りとして求めますが、ここでは b − a = −1 なので (b − a) × inv = −2 です。rem の結果は割られる数と同じ符号になるので -2 `rem` 5 は −2 で、答えは 2 + 3 × (−2) = −4 になります。
−4 も 3 で割ると 2 余り、5 で割ると 1 余るので、条件の余りそのものは満たしています。崩れているのは、0 以上 15 未満という範囲のほうです。b ≥ a の入力では (b − a) × inv が0以上になり、この欠陥は表に出ません。
Right
crt (a, m) (b, n) = a + m * ((b - a) * inv `mod` n)
mod の結果は割る数と同じ符号になるので、正の n で割れば t は必ず 0 以上 n 未満です。-2 `mod` 5 は 3 で、答えは 2 + 3 × 3 = 11 になります。t が 0 から n − 1 の範囲にあれば、a + m t は最大でも (m − 1) + m(n − 1) = mn − 1 なので、結果は 0 以上 m × n 未満に収まります。1
- Haskell の
remは0の方向へ切り捨てるquotと組で、C の%と同じ符号になります。modは負の無限大の方向へ切り捨てるdivと組です。どちらの組も、割られる数 = 商 × 割る数 + 余り を満たします。