求最大公约数【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) 可以通过以下步骤求得：
-
第一步：计算 a mod 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<<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、求最大公约数的几种常见的方法 【详解】