## 求最大公因子 ### Python代码 ```python def gcd(a, b): if b > a: return gcd(b, a) if b == 0: return a return gcd(b, a % b) ``` ### 原理 1. 设*a > b*，*a*和*b*的最大公因子为*c* 2. 如果*b*为0，则*c=a* 3. 令*a = k\*b + r*，由于*c|a*，*c|b*，故*c|r*（r=a%b） 4. 可以得出*c*是*b*与*r*的最大公因子，令*a, b = b, r*，返回第一步 ## 扩展欧几里得算法 ### 定义 > ax + by = gcd(a, b) ### Python代码 ```python def ex_gcd(a, b, xa=1, ya=0, xb=0, yb=1): if b > a: return ex_gcd(a, b) if b == 0: return a, xa, ya k = a // b x = xa - k * xb y = ya - k * yb return ex_gcd(b, a % b, xb, yb, x, y) ``` ### 原理 1. 设*a>b* 2. 根据*(a, b)->(b, r1)->(r1, r2)...(rn, 0)*，得*ri-2 = ki-2 \* ri-1 + ri* 3. 得*ri = ri-2 - ki-2 \* ri-1*，*ki-2 = ri-2 // ri-1* 4. 设*ri = xi\*a + yi\*b*，根据上一步得*xi = xi-2 - ki-2 \* xi-1*，*yi = yi-2 - ki-2 \* yi-1* 5. 当计算到*rn*时，*xn*和*yn*即为所求的*x*，*y*

创建时间：2023-06-10 | 最后修改：2023-12-27 | ©允许规范转载