欧几里得算法详解（包括扩展、同余方程）

1.普通欧几里得算法（求最大公约数）2.扩展欧几里得算法（求解a*x+b*y=c中（x，y））3.同余方程

1.普通欧几里得算法（求最大公约数）

欧几里得算法又称辗转相除法，可以用于快速的求取两个数的最大公约数

原理如下：

综上，gcd(a,b)=gcd(b,a%b)=…当b=0（即后一项为0时），a为gcd（前一项）。

最小公倍数 = a * b / gcd(a, b)

代码实现：

#include<stdio.h>int gcd(int a, int b){if(!b) return a;//递归的边界条件b=0时返回a值return gcd(b, a % b);//return (b ? gcd(b, a % b) : a); //另一种形式}int main(){int a, b;scanf("%d%d", &a, &b);printf("gcd(%d,%d)=%d\n", a, b, gcd(a,b));return 0;}

运行结果：

2.扩展欧几里得算法（求解ax+by=c中（x，y））

原理分析如下：

第一次方程为a * y + b * (x - ky) = 1 时，第二次方程即为 b * x + (a - kb) * y = 1.

注意x，y间的关系

ax + by = gcd(a, b)

代码实现如下：

#include<stdio.h>int ex_gcd(int a, int b, int *x, int *y) {if (!b) {*x = 1, *y = 0;return a;}//递归的边界条件b = 0时 x = 1，y任意int xx, yy, ret = ex_gcd(b, a % b, &xx, &yy);//自此往上的代码时层层递归，从第二层到边界条件//以下为层层回溯，由边界回溯至第二层，将值传给xx和yy，利用xy上下层的递推关系，x=yy，y=xx - k*yy*x = yy;*y = xx - (a / b) * yy;return ret;//另一种实现形式 注意值的替换/*int ret = ex_gcd(b, a % b, y, x);*y -= a / b * (*x);return ret;*/}int main() {int a, b, x, y;while (~scanf("%d%d", &a, &b)) {printf("gcd(%d, %d) = %d\n", a, b, ex_gcd(a, b, &x, &y));printf("%d * %d + %d * %d = %d\n", a, x, b, y, a * x + b * y);}return 0;}

代码运行结果：

3.同余方程

ax=1（mod b）求x的最小正整数解

原理分析见2

有解的条件为a，b互质

代码实现如下：

#include<stdio.h>void ex_gcd(int a, int b, int *x, int *y){if(b == 0){*x = 1;*y = 0;return;}int xx, yy;ex_gcd(b, a % b, &xx, &yy);*x = yy;*y = xx - a / b * yy;return;}int main(){int a, b, x, y;scanf("%d%d", &a, &b);ex_gcd(a, b, &x, &y);x = ((x % b) + b) % b;printf("%d * %d %% %d = 1\n", a, x, b);return 0;}

运行结果如下：