Function ext_gcd::ext_gcd

pub fn ext_gcd(a: i64, b: i64) -> (i64, i64, i64)

g = gcd(a, b), ax + by = g を満たす (x, y, g) を返します。

Examples

use ext_gcd::ext_gcd;

let (x, y, g) = ext_gcd(48, 30);
assert_eq!(g, 6);
assert_eq!(48 * x + 30 * y, g); // e.g. x = 2, y = -3

assert_eq!(ext_gcd(42, 0), (1, 0, 42));
assert_eq!(ext_gcd(0, 0), (0, 0, 0));