pub trait EquivMod: Sized {
// Required method
fn equiv_mod(self, other: Self) -> Option<Self>;
}Expand description
Chinese remaindering。
$\gdef{\lcm}{\operatorname{lcm}}$ $(r_0, m_0)$ と $(r_1, m_1)$ に対し、以下を満たす $0\le x\lt\lcm(m_0, m_1)$ を求める。
- $x\bmod m_0 = r_0$
- $x\bmod m_1 = r_1$
中国剰余定理から、$\gcd(m_0, m_1)=1$ であれば常に存在する。 そうでない場合、高々一つ存在する。
なお、計算の利便性のため、$\lcm(m_0, m_1)$ も返す。以下の例も参照。
Idea
$$ \begin{aligned} (y\cdot m_0+r_0)\bmod m_1 &= r_1 \\ (y\cdot m_0)\bmod m_1 &= (r_1-r_0)\bmod m_1 \\ \end{aligned} $$ $g = \gcd(m_0, m_1)$ として $(m_0, m_1) = (u_0g, u_1g)$ とすると、 $$ (y\cdot u_0g)\bmod u_1g = (r_1-r_0)\bmod u_1g. $$ 左辺は $g$ の倍数なので、右辺も $g$ の倍数となる必要がある。 よって、$r_1\not\equiv r_0\pmod{g}$ であれば解なしとなる。
以下、$r_1\equiv r_0\pmod{g}$ とする。このとき、$r_1-r_0$ は $g$ で割り切れ、 $$ \begin{aligned} (y\cdot u_0)\bmod u_1 &= \left(\frac{r_1-r_0}{g}\right)\bmod u_1 \\ y &\equiv \left(\frac{r_1-r_0}{g}\right)\cdot u_0^{-1} \pmod{u_1} \end{aligned} $$ となる。$\gcd(u_0, u_1)=1$ なので $u_0^{-1}$ は存在する。
これを満たす $0\le y\lt u_1$ は一意に定まり、$x = y\cdot m_0+r_0$ を計算すればよい。 また、$u_1 = m_1/g$ より、$\lcm(m_0, m_1) = m_0\cdot u_1$ となる。
Examples
use nekolib::math::EquivMod;
assert_eq!((0_i64, 2).equiv_mod((1, 3)), Some((4, 6)));
assert_eq!((0_i64, 2).equiv_mod((1, 4)), None);イテレータと組み合わせてもよい。 条件 $x\bmod 1 = 0$ が単位元となることに注意。
use nekolib::math::{EquivMod, Lcm};
let x = (2_i64..=20)
.map(|m| (m - 1, m))
.try_fold((0, 1), |x, y| x.equiv_mod(y));
let lcm = (2_i64..=20).fold(1, |x, y| x.lcm(y));
assert_eq!(x, Some((lcm - 1, lcm)));簡略版もある。
use nekolib::math::{EquivModIter, Lcm};
let x = (2_i64..=20).map(|m| (m - 1, m)).equiv_mod();
let lcm = (2_i64..=20).fold(1, |x, y| x.lcm(y));
assert_eq!(x, Some((lcm - 1, lcm)));
assert_eq!(std::iter::empty().equiv_mod(), Some((0_i32, 1)));