dsalgo 0.3.10

A package for Datastructures and Algorithms.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

use crate::{
    greatest_common_divisor_euclidean_recurse_i64::gcd,
    modular_inverse_euler_theorem_i64::modinv,
};

/// find a solution for ax = b (mod m)

pub fn mod_linear_equation(
    mut m: i64,
    mut a: i64,
    mut b: i64,
) -> Option<i64> {
    let g = gcd(m, a);

    if b % g != 0 {
        return None;
    }

    m /= g;

    a /= g;

    b /= g;

    let x = b * modinv(m, a) % m;

    Some((x + m) % m)
}

#[cfg(test)]

mod tests {

    use super::*;

    #[test]

    fn test() {
        // ref: https://atcoder.jp/contests/abc186/tasks/abc186_e
        let cases = vec![
            ((10, 4, 3), 2),
            ((1000, 11, 2), -1),
            ((998244353, 897581057, 595591169), 249561088),
            ((10000, 6, 14), 3571),
        ];

        for ((n, s, k), ans) in cases {
            let ans = if ans == -1 { None } else { Some(ans) };

            assert_eq!(mod_linear_equation(n, k, -s), ans);
        }
    }
}