pub fn extended_gcd(a: i64, b: i64) -> (i64, i64, i64)Expand description
Kengaytirilgan Evklid algoritmi: (g, x, y) shundayki a·x + b·y = g = gcd(a, b).
Nima uchun kerak: modul bo’yicha teskari element topish, diofant tenglamalar, RSA kabi kriptografik sxemalar.
§Misol
use rust_algorithms::numbers::extended_gcd;
let (g, x, y) = extended_gcd(240, 46);
assert_eq!(g, 2);
assert_eq!(240 * x + 46 * y, g);