Function cp_library_rs::number_theory::crt::garner_algorithm

pub fn garner_algorithm(rems: &[usize], mods: &[usize]) -> usize

中国剰余定理による整数の復元

中国剰余定理により，

$\mathrm{rems} = [r_1, r_2, \ldots, r_n], \mathrm{mods} = [m_1, m_2, \ldots, m_n]$ に対し，

• $x \equiv r_1 \mod m_1$
• $x \equiv r_2 \mod m_2$
• $\vdots$
• $x \equiv r_n \mod m_n$

を満たす $x$ を求める．

ただし，任意の $(i,j)$ に対し $m_i$ と $m_j$ は互いに素である必要がある．