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)));§Reference
§See also
Required Methods§
Dyn Compatibility§
This trait is not dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.