一、什么是公约数
公约数，也称为公因数，是指两个或多个整数共有的因数。具体来说，如果一个整数能被两个或多个整数整除，那么这个整数就是这些整数的公约数。
例如，考虑整数 12 和 18：
- 12 的因数有：1, 2, 3, 4, 6, 12
- 18 的因数有：1, 2, 3, 6, 9, 18
12 和 18 的公约数是它们共有的因数，即：1, 2, 3, 6
补充：最小公倍数 (LCM)
**定理：**a、b 两个数的最小公倍数 (lcm) 乘以它们的最大公约数 (gcd) 等于 a 和 b 本身的乘积。
如：gcd(a,b) * lcm(a,b) = a*b
所以，只要学会 gcd，lcm 就能直接推导出来：
lcm(a,b) = a*b / gcd(a,b)
二、计算最大公约数的方法
学习数论的一系列算法时，往往直接看算法是看不懂的。这里我们先学习数学解法，再给出算法实现。
1. 辗转相除法（欧几里得算法）
数学原理
假设我们有两个正整数 a 和 b，其中 a > b。根据辗转相除法，最大公约数 gcd(a,b) 可以通过以下步骤求得：
- 第一步：计算
a % b，得到余数 r。 - 第二步：将 a 替换为 b，将 b 替换为 r。
- 第三步：重复上述步骤，直到 b=0 时，此时 a 即为最大公约数。
下方用 (18, 12) 举例。
代码实现
#include <iostream>
using namespace std;
// 求公约数
int gcd(int a, int b){
while(a % b != 0){
int c = a % b;
a = b;
b = c;
}
return b;
}
int main(){
int a, b;
a = 18;
b = 12;
cout << gcd(a, b) << endl;
return 0;
}
2. 更相减损版（辗转相减法）
数学原理
更相减损法是一种古老的算法，用于求两个正整数的最大公约数（GCD）。它最早出现在中国古代数学著作《九章算术》中。
更相减损法的基本原理是：对于任意两个正整数 a 和 b（假设 a ≥ b），如果 a 和 b 都是偶数，则可以用 2 约简；如果 a 和 b 不都是偶数，则用较大的数减去较小的数，然后继续对所得的差和较小的数进行同样的操作，直到两个数相等为止。这个相等的数就是它们的最大公约数。
代码实现
#include <iostream>
using namespace std;
/**
* 函数功能：计算两个整数的最大公约数（Greatest Common Divisor, GCD）
* 参数：
* a: 第一个整数
* b: 第二个整数
* 返回值：
* a 和 b 的最大公约数
* 算法：采用更相减损术来计算最大公约数
*/
int func(int a, int b) {
// 只要 a 与 b 的差值不为 0，就持续循环
while (a - b != 0) {
// 计算 a 减去 b 的差值，并将结果存储在临时变量 c 中
int c = a - b;
// 把 b 的值赋给 a
a = b;
// 把差值 c 的值赋给 b
b = c;
}
// 当 a 与 b 的差值为 0 时，说明此时 a 和 b 相等，这个相等的值就是 a 和 b 的最大公约数
return a;
}
int main() {
int a, b;
a = 18;
b = 12;
cout << func(a, b) << endl;
return 0;
}
3. 其他方法
其他方法不像辗转相除法与更相减损法那么简便，在此简要介绍。
1. 分解质因数
#include <stdio.h>
void fun(int *arr, int n) {
int i = 2, j = 0;
while (n > 1) {
if (n % i == 0) {
arr[j++] = i;
n /= i;
} else {
i++;
}
}
}
int gcd(int a, int b) {
// 因为要进行找这个数的共有的因数，所以这里用数组来接收
int arr_a[100] = {0}; // 放 a 的所有因数
int arr_b[100] = {0}; // 放 b 的所有因数
// 进行放因数
fun(arr_a, a);
fun(arr_b, b);
// 找出公共的因数，然后相乘
int i = 0, j = 0, ret = 1;
while (arr_a[i] != 0 && arr_b[j] != 0) {
if (arr_a[i] == arr_b[j]) {
ret *= arr_a[i];
i++;
j++;
} else if (arr_a[i] > arr_b[j]) {
j++;
} else {
i++;
}
}
return ret;
}
int main() {
int a = 0;
int b = 0;
scanf("%d %d", &a, &b);
int ret = gcd(a, b); // 最大公因数
printf("%d 和%d的最大公因数是：%d", a, b, ret);
return 0;
}
2. 穷举法
法如其名，一个一个地输入测试，最后取出来。
#include <stdio.h>
int main() {
int a = 0;
int b = 0;
scanf("%d %d", &a, &b);
int t = a;
while (t--) {
if (a % t == 0 && b % t == 0) break;
}
printf("%d", t);
return 0;
}
3. 递归法
简单来说，递归法其实就是模拟了辗转相除法。
#include <iostream>
using namespace std;
int gcd(int a, int b) {
if (a % b == 0) {
return b;
} else {
return gcd(b, a % b);
}
}
int main() {
int a, b;
a = 18;
b = 12;
cout << gcd(a, b) << endl;
return 0;
}
三、练习：等差数列最短项数
题目描述 数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列，只记得其中 N 个整数。 现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？
输入描述 输入的第一行包含一个整数 N。 第二行包含 N 个整数 A1, A2, ..., AN。(注意 A1 ~ AN 并不一定是按等差数列中的顺序给出) 其中，2 ≤ N ≤ 10^5，0 ≤ Ai ≤ 10^9。
输出描述 输出一个整数表示答案。
这道题目难度适中，关键在于利用最大公约数求解公差。
- 很多人不会想到用 GCD 解题，甚至直接暴力解题。但可以利用最小差值作为间隔。
- 核心思路是求出所有相邻元素差值的最大公约数，即为公差 d。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 通过递归求最大公约数
int gcd(int a, int b) {
if (a % b == 0) {
return b;
} else {
return gcd(b, a % b);
}
}
int main() {
int n;
cin >> n;
vector<int> vec(n);
for (int i = 0; i < n; ++i) {
cin >> vec[i];
}
if (vec.size() == 2) {
// 特殊情况，只有两个数
cout << 2 << endl;
return 0;
}
sort(vec.begin(), vec.end());
vector<int> dif(n - 1);
// 差集数列
for (int i = 0; i < vec.size() - 1; ++i) {
dif[i] = vec[i + 1] - vec[i];
}
int d = dif[0];
if (d == 0) {
// 有没有一种可能，差值为 0（所有数相同）
cout << n << endl;
return 0;
}
// 所有差集的最大公约数即为公差
for (int i = 1; i < dif.size(); ++i) {
d = gcd(d, dif[i]);
}
int num = (vec[vec.size() - 1] - vec[0]) / d;
// d 为 0 的情况，已经被排除
if (num == 0) {
cout << vec.size() << endl;
} else {
cout << num + 1 << endl;
}
return 0;
}
总结
学习数论的一系列算法时，往往直接看算法是看不懂的。需要先摸清数学思想，胸有成竹之时，写对应算法就更轻松、也记得更牢固。别人算法理解不透的时候，往往是基础扎的不够牢固。
