pub fn solve_linear_congruence<T>(a: T, b: T, m: T) -> Option<(T, T)>where
T: Unsigned,Expand description
return: (y,z)
ax = b mod m, where x = y mod z
Examples found in repository?
crates/competitive/src/math/linear_congruence.rs (line 34)
21pub fn solve_simultaneous_linear_congruence<T, I>(abm: I) -> Option<(T, T)>
22where
23 T: Unsigned,
24 I: IntoIterator<Item = (T, T, T)>,
25{
26 let mut x = T::zero();
27 let mut m0 = T::one();
28 for (a, b, m) in abm {
29 let mut b = b + m - a * x % m;
30 if b >= m {
31 b -= m;
32 }
33 let a = a * m0;
34 let (y, z) = solve_linear_congruence(a, b, m)?;
35 x += y * m0;
36 m0 *= z;
37 }
38 x %= m0;
39 Some((x, m0))
40}