Trait nekolib::math::EquivMod

pub trait EquivMod: Sized {
    // Required method
    fn equiv_mod(self, other: Self) -> Option<Self>;
}

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

• https://github.com/atcoder/ac-library/blob/master/atcoder/math.hpp

See also

• https://rsk0315.hatenablog.com/entry/2021/01/18/065720#crt

Required Methods

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

Implementations on Foreign Types

impl EquivMod for (u32, u32)

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

impl EquivMod for (i64, i64)

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

impl EquivMod for (u8, u8)

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

impl EquivMod for (u64, u64)

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

impl EquivMod for (i128, i128)

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

impl EquivMod for (i16, i16)

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

impl EquivMod for (usize, usize)

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

impl EquivMod for (u16, u16)

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

impl EquivMod for (u128, u128)

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

impl EquivMod for (i32, i32)

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

impl EquivMod for (i8, i8)

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

impl EquivMod for (isize, isize)

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

Implementors