Appearance
若无特殊说明,本章涉及的变量皆为正整数。
最大公因数
若
递归到
时间复杂度为
cpp
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
最小公倍数
设
时间复杂度为
cpp
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
扩展欧几里得算法
扩展欧几里得算法用于求方程
设
设
由
因此,考虑先递归求解
边界条件:当递归到
cpp
struct Set {
int x, y;
Set(int x, int y) : x(x), y(y) {}
};
Set exGcd(int a, int b) { // 求解 ax + by = gcd(a, b)
if (b == 0)
return Set(1, 0);
Set ans = exGcd(b, a % b); // 先递归求解 bx + (a % b)y = gcd(b, a % b)
return Set(ans.y, ans.x - (a / b) * ans.y);
}