算法基础：数论
数论是纯粹数学的分支，主要研究整数的性质。在算法竞赛中，通常采取先使用、后证明的方式讲解。
1. 最大公约数和最小公倍数
约数和倍数
如果 a 除以 b 没有余数，那么 a 就是 b 的倍数，b 就是 a 的约数（也称因数），记作 b | a。
最大公约数和最小公倍数
- 最大公约数 (GCD)：一组整数的公约数中最大的一个。
- 最小公倍数 (LCM)：一组整数正的公倍数中最小的一个。
对于两个数 a 和 b，有性质：gcd(a, b) × lcm(a, b) = a × b。一般先求最大公约数，再利用此性质求最小公倍数。
欧几里得算法
欧几里得算法（辗转相除法）用于求两个整数的最大公约数。 算法流程：设 a > b：
- 如果 b 是 a 的约数，则 b 为最大公约数；
- 否则 gcd(a, b) = gcd(b, a mod b)。
由于 a mod b 会不断减小，可用递归求解。
long long gcd(long long a, long long b) {
if (!b) return a;
return gcd(b, a % b);
}
时间复杂度为 O(log n)。
例题：最大公约数
题目描述：输入三个正整数 x, y, z，求它们的最大公约数 g。 数据规模：1 ≤ x, y, z ≤ 10^6。
解法：三个数的最大公约数，先求其中两个的 gcd，再与第三个求 gcd。
#include <iostream>
using namespace std;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int main() {
int x, y, z;
cin >> x >> y >> z;
cout << ((x, y), z) << endl;
;
}
