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§

source

fn equiv_mod(self, other: Self) -> Option<Self>

Implementations on Foreign Types§

source§

impl EquivMod for (u32, u32)

source§

fn equiv_mod(self, other: Self) -> Option<Self>

source§

impl EquivMod for (i64, i64)

source§

fn equiv_mod(self, other: Self) -> Option<Self>

source§

impl EquivMod for (u8, u8)

source§

fn equiv_mod(self, other: Self) -> Option<Self>

source§

impl EquivMod for (u64, u64)

source§

fn equiv_mod(self, other: Self) -> Option<Self>

source§

impl EquivMod for (i128, i128)

source§

fn equiv_mod(self, other: Self) -> Option<Self>

source§

impl EquivMod for (i16, i16)

source§

fn equiv_mod(self, other: Self) -> Option<Self>

source§

impl EquivMod for (usize, usize)

source§

fn equiv_mod(self, other: Self) -> Option<Self>

source§

impl EquivMod for (u16, u16)

source§

fn equiv_mod(self, other: Self) -> Option<Self>

source§

impl EquivMod for (u128, u128)

source§

fn equiv_mod(self, other: Self) -> Option<Self>

source§

impl EquivMod for (i32, i32)

source§

fn equiv_mod(self, other: Self) -> Option<Self>

source§

impl EquivMod for (i8, i8)

source§

fn equiv_mod(self, other: Self) -> Option<Self>

source§

impl EquivMod for (isize, isize)

source§

fn equiv_mod(self, other: Self) -> Option<Self>

Implementors§