大家好啊，欢迎来到本博客( •̀ ω •́ )✧，我将带领大家详细的了解最大公约数的思想与解法。

一、什么是公约数

公约数，也称为公因数，是指两个或多个整数共有的因数。具体来说，如果一个整数能被两个或多个整数整除，那么这个整数就是这些整数的公约数。

例如，考虑整数12和18：

• 12的因数有 ：1, 2, 3, 4, 6, 12

• 18的因数有：1, 2, 3, 6, 9, 18

12和18的公约数是它们共有的因数，即：1, 2, 3, 6

---

二、计算最大公约数的方法：

学习数论的一系列算法时，往往直接看算法，是看不懂的。

这里我们先学习数学解法、在给出算法。

1、辗转相除法：（欧几里得算法）

数学：

假设我们有两个正整数 a 和 b，其中 a>b。根据辗转相除法，最大公约数 gcd(a,b) 可以通过以下步骤求得：

1. 第一步：计算 a mod b，得到余数 r。

2. 第二步：将 a 替换为 b，将 b 替换为 r。

3. 第三步：重复上述步骤，直到 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<<func(a,b)<<endl;
    return 0;
}

解释版：

// 包含输入输出流头文件，用于使用 cin 和 cout 进行输入输出操作
#include <iostream>

// 使用标准命名空间，这样就可以直接使用标准库中的类和函数，而无需加 std:: 前缀
using namespace std;

/**
 * 函数功能：计算两个整数的最大公约数（Greatest Common Divisor, GCD）
 * 参数：
 *      a: 第一个整数
 *      b: 第二个整数
 * 返回值：
 *      a 和 b 的最大公约数
 * 算法：使用欧几里得算法（辗转相除法）来计算最大公约数
 * 原理：两个整数 a 和 b（a > b）的最大公约数等于 b 和 a % b 的最大公约数
 */
int gcd(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;
    }
    // 当循环结束时，b 即为 a 和 b 的最大公约数，将其返回
    return b;
}

int main() {
    // 定义两个整型变量 a 和 b，用于存储要计算最大公约数的两个数
    int a, b;
    // 给变量 a 赋值为 18
    a = 18;
    // 给变量 b 赋值为 12
    b = 12;
    // 调用 gcd 函数计算 a 和 b 的最大公约数，并将结果输出到控制台
    cout << gcd(a, b) << endl;
    // 程序正常结束，返回 0 表示成功
    return 0;
}

2、更相减损版（辗转相减法）

数学：

更相减损法是一种古老的算法，用于求两个正整数的最大公约数（GCD）。它最早出现在中国古代数学著作《九章算术》中。以下是更相减损法的数学用法和原理：

更相减损法的基本原理是：对于任意两个正整数 a 和 b（假设 a≥b），如果 a 和 b 都是偶数，则可以用 2 约简；如果 a 和 b 不都是偶数，则用较大的数减去较小的数，然后继续对所得的差和较小的数进行同样的操作，直到两个数相等为止。这个相等的数就是它们的最大公约数。

如图：

代码：

简约背诵版： 

#include "iostream"
using namespace std;

int func(int a, int b){
    while(a-b!=0){
        int c = a - b;
        a = b;
        b = c;
    }
    return a;
}

int main(){
    int a,b;
    a = 18;
    b = 12;
    cout<<func(a,b)<<endl;
    return 0;
}

解释版：

// 引入标准输入输出流头文件，该头文件提供了像 cin 和 cout 这样的输入输出功能
// 注意：这里使用双引号包含头文件通常用于自定义头文件，标准库头文件一般用尖括号，应改为 #include <iostream>
#include "iostream"

// 使用标准命名空间 std，这样在后续代码里就可以直接使用标准库中的类和函数，无需添加 std:: 前缀
using namespace std;

/**
 * 函数名: func
 * 功能: 计算两个整数的最大公约数（Greatest Common Divisor, GCD）
 * 参数:
 *      a: 第一个整数
 *      b: 第二个整数
 * 返回值:
 *      a 和 b 的最大公约数
 * 算法: 采用更相减损术来计算最大公约数
 * 原理: 两个正整数 a 和 b（a > b）的最大公约数等于 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;
}

/**
 * 函数名: main
 * 功能: 程序的入口函数，程序从这里开始执行
 * 参数: 无
 * 返回值:
 *      整数 0，表示程序正常结束
 */
int main() {
    // 声明两个整型变量 a 和 b，用于存储要计算最大公约数的两个数
    int a, b;
    // 给变量 a 赋值为 18
    a = 18;
    // 给变量 b 赋值为 12
    b = 12;
    // 调用 func 函数计算 a 和 b 的最大公约数，并将结果输出到标准输出流（通常是控制台）
    // 输出完成后换行
    cout << func(a, b) << endl;
    // 返回 0 表示程序正常结束
    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{ // 余数为0进入递归
        return gcd(b,a%b); // b放到a的位置，a/b的余数放到b的位置 
    }
}
int main(){
    int a,b;
    a = 18;
    b = 12;
    cout<<gcd(a,b)<<endl;
    return 0;
}

三、练习：

等差数列

题目描述

数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一 部分的数列，只记得其中 NN 个整数。

现在给出这 NN 个整数，小明想知道包含这 NN 个整数的最短的等差数列有几项？

输入描述

输入的第一行包含一个整数 NN。

第二行包含 NN 个整数 A1,A2,⋅⋅⋅,ANA1​,A2​,⋅⋅⋅,AN​。(注意 A1A1​ ∼ ANAN​ 并不一定是按等差数列中的顺序给出)

其中，2≤N≤105，0≤Ai≤1092≤N≤105，0≤Ai​≤109。

输出描述

输出一个整数表示答案。

输入输出样例

示例

输入

5
2 6 4 10 20

输出

10

样例说明： 包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、 18、20

 这道题目说难不难，说简单不简单

1、很多人不会想到用gcd解题，甚至是直接暴力解题，欸！我一会也试试：(vec[n-1]-vec[0])/n,看来是不行的(n不是所有个数)。但是也能用最小差值作为间隔呀，如：d = min(d,gcd(dif[i],dif[i+1])); 这样好像也行，一会试试

2、当然就是这个啦d = min(d,vec[i+1]-vec[i]); 好多人没考虑min，细节容易出错。

#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=0; i<dif.size()-1; ++i){ // 所有差集的最大公约数
        d = min(d,gcd(dif[i],dif[i+1])); // 为防止结果处，出现更大的差值。
    }

    int num = (vec[vec.size()-1]-vec[0])/d; // d 为0的情况，已经被排除
    if(d==num){
        cout<<vec.size()<<endl;
    }else{
        cout<<num+1<<endl;
    }


    return 0;
}

---

笔者感悟：

学习数论的一系列算法时，往往直接看算法，是看不懂的。

需要先摸清数学思想，胸有成竹之时，写对应算法就更轻松、也记得更牢固。

别人算法理解不透的时候，往往是基础扎的不够牢固。

---

借鉴博客/视频：

1、求最大公约数的几种常见的方法 【详解】

---