网站内容规划,手机做公司网站,网站设计怎么做好,淘宝网页版登陆大家好啊#xff0c;欢迎来到本博客( •̀ ω •́ )✧#xff0c;我将带领大家详细的了解最大公约数的思想与解法。 一、什么是公约数
公约数#xff0c;也称为公因数#xff0c;是指两个或多个整数共有的因数。具体来说#xff0c;如果一个整数能被两个或多个整数整除欢迎来到本博客( •̀ ω •́ )✧我将带领大家详细的了解最大公约数的思想与解法。 一、什么是公约数
公约数也称为公因数是指两个或多个整数共有的因数。具体来说如果一个整数能被两个或多个整数整除那么这个整数就是这些整数的公约数。
例如考虑整数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其中 ab。根据辗转相除法最大公约数 gcd(a,b) 可以通过以下步骤求得 第一步计算 a mod b得到余数 r。 第二步将 a 替换为 b将 b 替换为 r。 第三步重复上述步骤直到 b0 时此时 a 即为最大公约数。
下方用18、12举例。
如图 代码
简约背诵版
#include iostream
using namespace std;
// 求公约数
int gcd(int a, int b){while(a%b!0){int c a%b;ab;bc;}return b;
}int main(){int a,b;a 18;b 12;coutfunc(a,b)endl;return 0;
}解释版
// 包含输入输出流头文件用于使用 cin 和 cout 进行输入输出操作
#include iostream// 使用标准命名空间这样就可以直接使用标准库中的类和函数而无需加 std:: 前缀
using namespace std;/*** 函数功能计算两个整数的最大公约数Greatest Common Divisor, GCD* 参数* a: 第一个整数* b: 第二个整数* 返回值* a 和 b 的最大公约数* 算法使用欧几里得算法辗转相除法来计算最大公约数* 原理两个整数 a 和 ba 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;coutfunc(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 和 ba 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、分解质因数 #includestdio.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、穷举法
法如其名一个一个的输入测试最后取出来。
//穷举法
#includestdio.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%b0){ // 得到余数return b;}else{ // 余数为0进入递归return gcd(b,a%b); // b放到a的位置a/b的余数放到b的位置 }
}
int main(){int a,b;a 18;b 12;coutgcd(a,b)endl;return 0;
}
三、练习 等差数列 题目描述 数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一 部分的数列只记得其中 NN 个整数。 现在给出这 NN 个整数小明想知道包含这 NN 个整数的最短的等差数列有几项 输入描述 输入的第一行包含一个整数 NN。 第二行包含 NN 个整数 A1,A2,⋅⋅⋅,ANA1,A2,⋅⋅⋅,AN。(注意 A1A1 ∼ ANAN 并不一定是按等差数列中的顺序给出) 其中2≤N≤1050≤Ai≤1092≤N≤1050≤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[i1])); 这样好像也行一会试试
2、当然就是这个啦d min(d,vec[i1]-vec[i]); 好多人没考虑min细节容易出错。
#include iostream
#include vector
#include algorithm
using namespace std;// 通过递归
int gcd(int a, int b){if(a%b0){return b;}else{return gcd(b,a%b);}
}int main()
{int n;cinn;vectorint vec(n);for(int i0; in; i){cinvec[i];}if(vec.size()2){ // 特殊情况只有两个数cout2endl;return 0;}sort(vec.begin(), vec.end());vectorint dif(n-1); // 差集数列for(int i0; ivec.size()-1; i){dif[i] vec[i1]-vec[i];}int d dif[0];if(d0){ // 有没有一种可能差值为0。coutnendl;return 0;}for(int i0; idif.size()-1; i){ // 所有差集的最大公约数d min(d,gcd(dif[i],dif[i1])); // 为防止结果处出现更大的差值。}int num (vec[vec.size()-1]-vec[0])/d; // d 为0的情况已经被排除if(dnum){coutvec.size()endl;}else{coutnum1endl;}return 0;
} 笔者感悟
学习数论的一系列算法时往往直接看算法是看不懂的。
需要先摸清数学思想胸有成竹之时写对应算法就更轻松、也记得更牢固。
别人算法理解不透的时候往往是基础扎的不够牢固。 借鉴博客/视频
1、求最大公约数的几种常见的方法 【详解】
