41 lines
882 B
Text
41 lines
882 B
Text
fn egcd(a: i64, b: i64) -> (i64, i64, i64) {
|
|
if a == 0 {
|
|
(b, 0, 1)
|
|
} else {
|
|
let (g, x, y) = egcd(b % a, a);
|
|
(g, y - (b / a) * x, x)
|
|
}
|
|
}
|
|
|
|
fn mod_inv(x: i64, n: i64) -> Option<i64> {
|
|
let (g, x, _) = egcd(x, n);
|
|
if g == 1 {
|
|
Some((x % n + n) % n)
|
|
} else {
|
|
None
|
|
}
|
|
}
|
|
|
|
fn chinese_remainder(residues: &[i64], modulii: &[i64]) -> Option<i64> {
|
|
let prod = modulii.iter().product::<i64>();
|
|
|
|
let mut sum = 0;
|
|
|
|
for (&residue, &modulus) in residues.iter().zip(modulii) {
|
|
let p = prod / modulus;
|
|
sum += residue * mod_inv(p, modulus)? * p
|
|
}
|
|
|
|
Some(sum % prod)
|
|
}
|
|
|
|
fn main() {
|
|
let modulii = [3,5,7];
|
|
let residues = [2,3,2];
|
|
|
|
match chinese_remainder(&residues, &modulii) {
|
|
Some(sol) => println!("{}", sol),
|
|
None => println!("modulii not pairwise coprime")
|
|
}
|
|
|
|
}
|