求最大公约数【C/C++】

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

一、什么是公约数

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

例如，考虑整数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 的值赋给 aa = b;// 将余数 c 的值赋给 bb = c;}// 当循环结束时，b 即为 a 和 b 的最大公约数，将其返回return b;
}int main() {// 定义两个整型变量 a 和 b，用于存储要计算最大公约数的两个数int a, b;// 给变量 a 赋值为 18a = 18;// 给变量 b 赋值为 12b = 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 的值赋给 aa = b;// 把差值 c 的值赋给 bb = c;}// 当 a 与 b 的差值为 0 时，说明此时 a 和 b 相等，这个相等的值就是 a 和 b 的最大公约数，将其返回return a;
}/*** 函数名: main* 功能: 程序的入口函数，程序从这里开始执行* 参数: 无* 返回值:*      整数 0，表示程序正常结束*/
int main() {// 声明两个整型变量 a 和 b，用于存储要计算最大公约数的两个数int a, b;// 给变量 a 赋值为 18a = 18;// 给变量 b 赋值为 12b = 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、求最大公约数的几种常见的方法 【详解】

---