最大公约 Greatest Common Divisor GCD
欧几里得算法
// C++ Version
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
算法复杂度是 \(O(\log n)\).
习题
- P8255 [NOI Online 2022 入门组] 数学游戏 提高+/省选-
// C++ Version
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
算法复杂度是 \(O(\log n)\).