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 31)
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 b = b.mod_sub(a.mod_mul(x, m), m);
30 let a = a * m0;
31 let (y, z) = solve_linear_congruence(a, b, m)?;
32 x += y * m0;
33 m0 *= z;
34 }
35 x %= m0;
36 Some((x, m0))
37}