haar_lib/math/
linear_indeterminate_equation.rs

1//! 一次不定方程式$ax + by = c$
2use crate::math::ext_gcd::ext_gcd;
3
4/// 一次不定方程式$ax + by = c (a, b \neq 0)$を解く。
5///
6/// 方程式が解を持たないとき、`None`を返す。
7///
8/// 解を持つとき、`Some((x0, y0, s, t))`を返す。
9/// $
10/// \begin{cases}
11/// x &= x_0 + s \times k \\\\
12/// y &= y_0 + t \times k
13/// \end{cases}
14/// (k \in \mathbb{Z})$は方程式の一般解である。
15/// $x_0, y_0$は解のうち$x$が非負で最小のものである。
16pub fn linear_indeterminate_equation(a: i64, b: i64, c: i64) -> Option<(i64, i64, i64, i64)> {
17    assert_ne!(a, 0);
18    assert_ne!(b, 0);
19
20    let (g, mut x, _) = ext_gcd(a.unsigned_abs(), b.unsigned_abs());
21
22    if c % g != 0 {
23        return None;
24    }
25
26    let mut dx = b / g;
27    let mut dy = -a / g;
28    let dc = c / g;
29
30    x %= dx;
31    if x < 0 {
32        x += dx.abs();
33    }
34
35    x *= dc;
36
37    let y = (c - a * x) / b;
38
39    if dx < 0 {
40        dx = -dx;
41        dy = -dy;
42    }
43
44    Some((x, y, dx, dy))
45}
46
47#[cfg(test)]
48mod tests {
49    use super::*;
50
51    #[test]
52    fn test() {
53        let (a, b, c) = (111, 30, 12);
54        let (x0, y0, s, t) = linear_indeterminate_equation(a, b, c).unwrap();
55
56        for k in -100..=100 {
57            let x = x0 + s * k;
58            let y = y0 + t * k;
59            assert_eq!(a * x + b * y, c);
60        }
61    }
62}
haar_lib/math/linear_indeterminate_equation.rs

haar_lib/math/
linear_indeterminate_equation.rs
