自然数/整数 - その他定理 - 中国人剰余定理

概要

\(N\) 個の整数ペア \((r_1, m_1), \ldots, (r_N, m_N)\) （ただし \(m_i\) は非負）について \[x = r_i \bmod m_i ~~ \forall i=1,2,\ldots,N\] を満たすような整数 \(x\) は存在するなら一般に \[x = y \bmod z\] の形で与えられる.

このライブラリは \((r_i, m_i)\) から \((y,z)\) を計算する.

use crate::num::base::*;
use crate::num::gcd_ex::*;

/// Number Theory - Chinese Remainder Theorem (CRT)
/// Solve of x = r[i] mod m[i] => x = y mod z
/// - Args:
///     - rm: &Vec of pair (r[i], m[i])
/// - Returns Some(y, z)
pub fn crt<X: Num>(rm: &[(X, X)]) -> Option<(X, X)> {
    assert!(!rm.is_empty());
    for &(_, m) in rm.iter() {
        assert!(m > X::zero());
    }
    let mut r0 = X::zero();
    let mut m0 = X::one();
    for &(r, m) in rm.iter() {
        let (p, _, d) = gcd_ex(m0, m);
        if (r - r0) % d != X::zero() {
            return None;
        }
        let tmp = (r - r0) / d * p % (m / d);
        r0 += m0 * tmp;
        m0 *= m / d;
    }
    while r0 < X::zero() {
        r0 += m0
    }
    Some((r0, m0))
}

#[cfg(test)]
mod test_crt {
    use crate::num::chinese_remainder_theorem::*;
    #[test]
    fn it_works() {
        assert_eq!(crt::<i64>(&vec![(1, 2)]), Some((1, 2)));
        assert_eq!(crt::<i64>(&vec![(1, 2), (2, 3)]), Some((5, 6)));
        assert_eq!(crt::<i64>(&vec![(1, 3), (2, 3)]), None);
        assert_eq!(crt::<i64>(&vec![(1, 3), (2, 5)]), Some((7, 15)));
        assert_eq!(crt::<i64>(&vec![(1, 3), (2, 5), (3, 7)]), Some((52, 105)));
        assert_eq!(crt::<i64>(&vec![(2, 3), (2, 5), (3, 7)]), Some((17, 105)));
        assert_eq!(
            crt::<i64>(&vec![(1, 4), (0, 13), (14, 17)]),
            Some((65, 884))
        );
        assert_eq!(
            crt::<i128>(&vec![(1, 4), (1, 8), (0, 13), (14, 17)]),
            Some((65, 1768))
        );
    }
}