haar_lib/math/
linear_congruence.rs

1//! 一次合同方程式を解く。
2use crate::math::{gcd_lcm::*, mod_ops::inv::*};
3
4/// ax + b = 0 (mod m) を満たすxを求める。
5pub fn linear_congruence(mut a: i64, mut b: i64, mut m: u64) -> Option<i64> {
6    if a >= m as i64 {
7        a %= m as i64;
8    }
9    if b >= m as i64 {
10        b %= m as i64;
11    }
12    if a < 0 {
13        a += m as i64;
14        a %= m as i64;
15    }
16    if b < 0 {
17        b += m as i64;
18        b %= m as i64;
19    }
20
21    let mut a = a as u64;
22    let mut b = b as u64;
23    let g = a.gcd(m);
24    if b % g == 0 {
25        a /= g;
26        b /= g;
27        m /= g;
28    }
29
30    Some(((m - b) * mod_inv(a, m)? % m) as i64)
31}
32
33#[cfg(test)]
34mod tests {
35    use super::*;
36
37    #[test]
38    fn test() {
39        let m = 100;
40
41        for a in 1..=100 {
42            for b in 0..=100 {
43                if let Some(x) = linear_congruence(a, b, m) {
44                    assert_eq!((a * x + b) % m as i64, 0);
45                } else {
46                    assert!((0..m).all(|x| (a * x as i64 + b) % m as i64 != 0));
47                }
48            }
49        }
50    }
51}
haar_lib/math/linear_congruence.rs

haar_lib/math/
linear_congruence.rs
