文章目录普通欧几里得算法扩展欧几里得算法算法文字描述算法c语言二进制扩展欧几里得算法二进制扩展欧几里得算法求 a/b mod p 二进制扩展欧几里得算法求 1/b mod p 性质欧几里得算法。一个常见误区有人以为 gcd(a,b)1 是 a/bmodp 可计算的必要条件。其实不然只要 gcd(b,p)1 就足够了gcd(a,b) 是否为 1 不影响模逆的存在性。普通欧几里得算法求最大公约数gcd普通欧几里得定义gcd(a,b)gcd(b,a mod b)直到余数为 0最后一个非零余数就是最大公约数。 gcd(48,18) 48%1812 gcd(18,12) 18%126 gcd(12,6) 12%60 故gcd(48,18) gcd(12,6) 6 int gcd(int a, int b) { int temp; while (b ! 0) { temp a % b; a b; b temp; } return a; } 递归版本 int gcd(int a, int b) { if (b 0) return a; return gcd(b, a % b); }扩展欧几里得算法扩展欧几里得算法通过不断用“较大数减去较小数的倍数”来简化问题并在每一步保持 axby的值不变最终把这个值收缩到 gcd(a,b)同时得到对应的系数。其核心思想是维护不变式在每一步中当前余数都能表示为输入整数 a和 b的线性组合且系数随余数同步更新。作用不仅能算出最大公约数还能直接构造出贝祖等式 axbygcd(a,b)的整数解。求逆元解线性不定方程算法文字描述已知ab 求得到最大公约数 gcd(a,b)以及满足 a·x1 b·y1 gcd(a,b)的整数 x1、y1。 定义中间辅助变量 x2、y2 非递归版本本质上就是在从底向上模拟递归的回推过程只是没有用函数栈。 数学上等价于 新系数上一轮系数−q×当前系数 初始化 a 48, b 18 x1 1, y1 0对应 a的系数 x2 0, y2 1对应 b的系数 循环条件b ≠ 0每次迭代 计算商 q a // b 更新 (a , b ) (b , a - q·b ) 更新 (x1, x2) (x2, x1 - q·x2) 更新 (y1, y2) (y2, y1 - q·y2) 循环结束时a即为 gcd此时 x1、y1即为所求系数。 初始化 x11,y10 x20,y21 gcd(48,18) q48//182 b48%1848-2*1812; a18 (x1,x2) (x2,x1-2*x2) (0,1-2*0)(0,1) (y1,y2) (y2,y1-q·y2)(1,0-2*1)(1,-2) gcd(18,12) q18//121 b18%1218-1*126; a12 (x1,x2) (x2,x1-2*x2) (1,0-1*1)(1,-1) (y1,y2) (y2,y1-q·y2)(-2,1-1*(-2))(-2,3) gcd(12,6) q12//62 b12%612-2*60; a12 (x1,x2) (x2,x1-2*x2) (-1,1-2*(-1))(-1,3) (y1,y2) (y2,y1-q·y2)(-3,-2-2*3)(3,-8) gcd(48,18) 6 48 * (-1) 18 * 3迭代计算过程迭代abq a // b新 a新 bx1x2y1y2初始4818———10011481821812011-22181211261-1-233126260-133-8算法c语言一边做辗转相除一边同步构造贝祖系数。 // 非递归版扩展欧几里得算法 // 返回 gcd(a, b)并得到 ax by gcd 的一组解 int extended_gcd(int a, int b, int *x, int *y) { int x0 1, y0 0; // 初始a*1 b*0 a int x1 0, y1 1; // a*0 b*1 b int r0 a, r1 b; int q, tmp; while (r1 ! 0) { q r0 / r1; // 余数迭代 tmp r1; r1 r0 % r1; r0 tmp; // 系数迭代 tmp x1; x1 x0 - q * x1; x0 tmp; tmp y1; y1 y0 - q * y1; y0 tmp; } *x x0; *y y0; return r0; } 递归 // 返回 gcd(a, b)并通过指针 x, y 得到方程 ax by gcd 的一组解 int extended_gcd(int a, int b, int *x, int *y) { if (b 0) { *x 1; *y 0; return a; } int x1, y1; int gcd extended_gcd(b, a % b, x1, y1); *x y1; *y x1 - (a / b) * y1; return gcd; }二进制扩展欧几里得算法二进制扩展欧几里得算法求 a/b mod p 二进制扩展欧几里得算法求 1/b mod p 求1/b mod p与gcdb,p有什么关系性质“边求 gcd 边求逆” 的精髓是二进制 GCD 的每一步归约操作去 2、凑偶、大减小都被精心设计成不改变线性组合不变式的变换。当 gcd 被归约为 1 的那一刻不变式本身就变成了逆元的定义式 b⋅x≡1(modp)。gcd 与逆元不是先后两步而是同一个过程的同一个输出——这正是二进制扩展欧几里得算法最漂亮的地方。// 二进制扩展欧几里得非递归 // 返回 gcd(a,b)并满足 a*x b*y gcd(a,b) int binary_exgcd(int a, int b, int *x, int *y) { int g 1, u a, v b; int x1 1, y1 0, x2 0, y2 1; while ((u 1) 0 (v 1) 0)//两个偶数 u 1, v 1, g 1; *x x1, *y y1; while (u) { while ((u 1) 0) { u 1; if ((*x 1) || (*y 1)) *x (*x v) 1, *y (*y - u) 1; else *x 1, *y 1; } while ((v 1) 0) { v 1; if ((x2 1) || (y2 1)) x2 (x2 u) 1, y2 (y2 - v) 1; else x2 1, y2 1; } if (u v) u - v, *x - x2, *y - y2; else v - u, x2 - *x, y2 - *y; } *x x2 * g; *y y2 * g; if (a 0) *x -*x; if (b 0) *y -*y; return v * g; }