cp_library_rs/number_theory/
crt.rs

1//! 中国剰余定理
2//!
3//! Garnerのアルゴリズムによる中国剰余定理の解復元
4
5use crate::number_theory::ext_euclid::inv;
6
7/// 中国剰余定理による整数の復元
8///
9/// 中国剰余定理により，
10///
11/// $`\mathrm{rems} = [r_1, r_2, \ldots, r_n], \mathrm{mods} = [m_1, m_2, \ldots, m_n]`$ に対し，
12/// - $`x \equiv r_1 \mod m_1`$
13/// - $`x \equiv r_2 \mod m_2`$
14/// - $`\vdots`$
15/// - $`x \equiv r_n \mod m_n`$
16///
17/// を満たす $`x`$ を求める．
18///
19/// ただし，任意の $`(i,j)`$ に対し $`m_i`$ と $`m_j`$ は互いに素である必要がある．
20pub fn garner_algorithm(rems: &[usize], mods: &[usize]) -> usize {
21    let mut m = 1;
22    let mut x = (rems[0] % mods[0]) as isize;
23
24    for i in 0..rems.len() {
25        let (ri, mi) = (rems[i] as isize, mods[i] as isize);
26        let Some(inv_m) = inv(m, mi) else {
27            panic!("For all (i,j), gcd(mi, mj) must be 1.")
28        };
29        let t = ((ri - x) * inv_m).rem_euclid(mi);
30        x += t * m;
31        m *= mi;
32    }
33    x as usize
34}
cp_library_rs/number_theory/crt.rs

cp_library_rs/number_theory/
crt.rs
