acm/
integers.rs

1pub trait GCD {
2    // Extended Euclidean algorithm
3    fn gcd(self, other: Self) -> Self;
4}
5
6impl<T: Into<i32> + From<i32>> GCD for T {
7    fn gcd(self, other: Self) -> Self {
8        let a: i32 = self.into();
9        let b: i32 = other.into();
10        let mut prev = [a, 1, 0];
11        let mut curr = [b, 0, 1];
12        while curr[0] != 0 {
13            let q = prev[0] / curr[0];
14            for i in 0..2 {
15                let temp = curr[i];
16                curr[i] = prev[i] - q * temp;
17                prev[i] = temp;
18            }
19        }
20        prev[0].into()
21    }
22}