求最大公约数(gcd)与最小公倍数(lcm)【C/C++】

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

一、什么是公约数

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

例如，考虑整数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) 可以通过以下步骤求得：

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。

输出描述

输出一个整数表示答案。

输入输出样例

示例输入输出样例说明： 包含 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、求最大公约数的几种常见的方法 【详解】