14 lines
613 B
Rust
14 lines
613 B
Rust
use std::cmp::{min, max};
|
|
fn gcd(a: usize, b: usize) -> usize {
|
|
match ((a, b), (a & 1, b & 1)) {
|
|
((x, y), _) if x == y => y,
|
|
((0, x), _) | ((x, 0), _) => x,
|
|
((x, y), (0, 1)) | ((y, x), (1, 0)) => gcd(x >> 1, y),
|
|
((x, y), (0, 0)) => gcd(x >> 1, y >> 1) << 1,
|
|
((x, y), (1, 1)) => { let (x, y) = (min(x, y), max(x, y));
|
|
gcd((y - x) >> 1, x)
|
|
}
|
|
_ => unreachable!(),
|
|
}
|
|
}
|