- 又称辗转相除法，是指用于计算两个正整数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)
（扩展）欧几里得算法
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 欧几里得算法欧几里得算法 (Euclidean algorithm) 是用来解决最大公约数问题的，通常采用辗转相除...
