扩展欧几里得算法

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. }