- 又称辗转相除法，是指用于计算两个正整数a，b的最大公约数 (GCD, Greatest Common Divisor)，扩展欧几里得除了求出最大公约数，还找出相应的x，y（其中一个很可能是负数）(
, 通常扩展欧几里得算法里我们使用的
)
- 欧几里得算法
- C++17中numeric头文件中已经包含了gcd这个函数: https://en.cppreference.com/w/cpp/numeric/gcd
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
- 扩展欧几里得算法
- 贝祖等式（贝祖定理）：是一个关于最大公约数的定理，对任何整数a，b和它们的最大公约数d，方程
有整数解当且仅当m是d的倍数（扩展欧几里得求逆元中我们取这个倍数为1，即m=d）
int egcd(int a, int b, int &x, int &y) { if (b == 0) { x = 1; y = 0; return a; } int nx, ny; // b*nx + a%b*ny = q int q = egcd(b, a % b, nx, ny); // a*x + b*y // = a*ny + b*nx - b*(a/b)*ny // = b*nx + (a - b*(a/b))*ny // = b*nx + a%b*ny // = q x = ny; y = nx - (a / b) * ny; return q; }- 这里如果q=1, 即上面求的x，y是对应了等式
，可以求逆元
/** * @returns (x % b + b) % b where a*x + by = gcd(a, b) */ int mod_inv(int a, int b) { int x, y; egcd(a, b, x, y); return (x % b + b) % b; // possible that x < 0 }
- 贝祖等式（贝祖定理）：是一个关于最大公约数的定理，对任何整数a，b和它们的最大公约数d，方程
- 扩展
- 求最小公倍数lcm (c++17中的numeric头文件也已经有了lcm这个函数)
- 有了最大公约数，求最小共倍数 (LCM, Least Common Multiple)就是:
a * b / gcd(a, b)
网友评论