扩展欧几里得算法

  1. fn update_step(a: &mut i32, old_a: &mut i32, quotient: i32) {
  2.     let temp = *a;
  3.     *a = *old_a - quotient * temp;
  4.     *old_a = temp;
  5. }
  7. pub fn extended_euclidean_algorithm(a: i32, b: i32) -> (i32, i32, i32) {
  8.     let (mut old_r, mut rem) = (a, b);
  9.     let (mut old_s, mut coeff_s) = (1, 0);
  10.     let (mut old_t, mut coeff_t) = (0, 1);
  12.     while rem != 0 {
  13.         let quotient = old_r / rem;
  15.         update_step(&mut rem, &mut old_r, quotient);
  16.         update_step(&mut coeff_s, &mut old_s, quotient);
  17.         update_step(&mut coeff_t, &mut old_t, quotient);
  18.     }
  20.     (old_r, old_s, old_t)
  21. }
  23. #[cfg(test)]
  24. mod tests {
  25.     use super::*;
  27.     #[test]
  28.     fn basic() {
  29.         assert_eq!(extended_euclidean_algorithm(101, 13), (1, 4, -31));
  30.         assert_eq!(extended_euclidean_algorithm(123, 19), (1, -2, 13));
  31.         assert_eq!(extended_euclidean_algorithm(25, 36), (1, 13, -9));
  32.         assert_eq!(extended_euclidean_algorithm(69, 54), (3, -7, 9));
  33.         assert_eq!(extended_euclidean_algorithm(55, 79), (1, 23, -16));
  34.         assert_eq!(extended_euclidean_algorithm(33, 44), (11, -1, 1));
  35.         assert_eq!(extended_euclidean_algorithm(50, 70), (10, 3, -2));
  36.     }
  37. }