-
Notifications
You must be signed in to change notification settings - Fork 7
/
13.rs
43 lines (37 loc) · 1.09 KB
/
13.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
use std::io::stdin;
fn mod_inv(a: i64, module: i64) -> i64 {
let mut mn = (module, a);
let mut xy = (0, 1);
while mn.1 != 0 {
xy = (xy.1, xy.0 - (mn.0 / mn.1) * xy.1);
mn = (mn.1, mn.0 % mn.1);
}
while xy.0 < 0 {
xy.0 += module;
}
xy.0
}
fn chinese_remainder_theorem(pairs: &Vec<(i64, i64)>) -> i64 {
let prod: i64 = pairs.iter().map(|t| t.1).product();
let mut sum = 0;
for (s, x) in pairs {
let p = prod / x;
let residue = (x - s) % x;
sum += residue * mod_inv(p, *x) * p;
}
sum % prod
}
fn main() {
let lines = stdin().lines().filter_map(Result::ok).collect::<Vec<_>>();
let time: i32 = lines.first().unwrap().parse().unwrap();
lines[1].split(",")
.filter_map(|s| s.parse().ok())
.map(|t: i32| (t - time % t, t))
.min()
.map(|(b, t)| println!("{}", b*t));
let pairs = lines[1].split(",")
.enumerate()
.filter_map(|(i, s)| s.parse().ok().map(|n| (i as i64, n)))
.collect::<Vec<_>>();
println!("{:?}", chinese_remainder_theorem(&pairs));
}