首页 > 代码库 > 欧几里得算法和扩展欧几里得算法

欧几里得算法和扩展欧几里得算法

技术分享

技术分享

技术分享

 1
实现代码:
#include <iostream> 2 using namespace std; 3 4 void exgcd(long long a, long long b, long long &d, long long &x, long long &y) { 5 if (b == 0) { 6 d = a, x = 1, y = 0; 7 } 8 else { 9 exgcd(b, a%b, d, y, x); y-=a/b*x; 10 } 11 } 12 13 int main() { 14 long long a, b, d, x, y; 15 while (cin >> a >> b) { 16 exgcd(a, b, d, x, y); 17 cout << d << " " << x << " " << y << endl; 18 } 19 20 }

 

欧几里得算法和扩展欧几里得算法