competitive_programming_rs/math/
chinese_remainder_theorem.rs

1pub fn extended_gcd(a: i64, b: i64) -> (i64, i64, i64) {
2    if b == 0 {
3        (a, 1, 0)
4    } else {
5        let (d, q, p) = extended_gcd(b, a % b);
6        (d, p, q - a / b * p)
7    }
8}
9
10pub fn chinese_remainder_theorem(b: &[i64], modulo: &[i64]) -> Option<(i64, i64)> {
11    let (mut result, mut m) = (0, 1);
12    for i in 0..b.len() {
13        let (d, p, _) = extended_gcd(m, modulo[i]);
14        if (b[i] - result) % d != 0 {
15            return None;
16        }
17        let tmp = ((b[i] - result) / d * p) % (modulo[i] / d);
18        result += m * tmp;
19        m *= modulo[i] / d;
20    }
21    Some(((result % m + m) % m, m))
22}
23
24#[cfg(test)]
25mod tests {
26    use super::*;
27    use rand;
28    use rand::Rng;
29
30    #[test]
31    fn test_extended_gcd() {
32        for i in 1..10000 {
33            for j in (i + 1)..10000 {
34                let (gcd, x, y) = extended_gcd(i, j);
35                assert_eq!(i % gcd, 0);
36                assert_eq!(j % gcd, 0);
37                assert_eq!(i * x + j * y, gcd);
38            }
39        }
40    }
41
42    #[test]
43    fn test_crt() {
44        let mut rng = rand::thread_rng();
45        let n = 10;
46        let max_m = 100;
47        for _ in 0..1000 {
48            let ans = rng.gen::<u32>() as i64;
49            let mut b = vec![0; n];
50            let mut m = vec![0; n];
51            for i in 0..n {
52                m[i] = rng.gen::<u8>() as i64;
53                m[i] %= max_m;
54                m[i] += 1;
55                b[i] = ans % m[i];
56            }
57
58            let (a, _) = chinese_remainder_theorem(&b, &m).unwrap();
59            for i in 0..n {
60                assert_eq!(a % m[i], b[i]);
61            }
62        }
63    }
64}
competitive_programming_rs/math/chinese_remainder_theorem.rs

competitive_programming_rs/math/
chinese_remainder_theorem.rs
