小小GCD、LCM拿下拿下

目录

最大公约数（GCD）

最大公约数（GCD）求解：

一、辗转相除法

二、三目运算符

三、位运算

最大公约数（GCD）模板： 

最大公约数（GCD）例题：

最小公倍数（LCM）

最小公倍数（LCM）求解：

最小公倍数（LCM）模板：

最小公倍数（LCM）例题：

---

GCD、LCM是算法当中的基础之基础，分别对应最大公约数、最小公倍数，在算法竞赛中涉及到的概率也是比较高的，GCD、LCM在小学时就涉及到了求法，本篇将给大家详解GCD、LCM这两个函数，并且提供最简单的模板，在考察时，直接背上即可。

最大公约数（GCD）

也称为最大公因数或最大公因子，是指两个或多个整数共有的约数中最大的一个。在数学中，这是指能够同时被这些整数整除的最大的正整数。例如，8与12的最大公约数为4，4同时能够被8与12整除，找不到x>4同时满足8%x=0且12%x=0这样的数，我们就认为4是8与12的最大公约数（GCD）

最大公约数（GCD）求解：

一、辗转相除法

我们求解最大公约数（GCD）最常用的方法为辗转相除法，就跟小学学的方法一样，具体思路为：设两数为n、m(n>m)， 用n除以m，r1为余数：即a÷b=q.....r1。若r1=0，则gcd(a，b)=b;若r1≠0，则再用b除以r1（辗转一下），r2为余数：即b÷r1=q.......r2 。若r2=0，则gcd(a，b)=r1，若r2≠0，则继续用r1除以r2，如此下去，直到能整除为止。其最后一个为被除数的余数的除数即为gcd(a, b)。

例如:a=12,b=8，a%b=4,b%4=0,最后一个为被除数余数的除数就是4,4就是所求最大公约数。

二、三目运算符

实际上，这两种写法在功能上是等价的，都是运用了辗转相除法,都能正确计算出两个整数的最大公约数。它们只是条件判断的表达方式不同，这里的判断条件变为了n>0。不过，第一种写法在n为0时直接返回结果，避免了一次递归调用，可能会有微小的性能优势。但在实际应用中，这种差异通常可以忽略不计，大家觉得哪个好记就记哪个就行。

三、位运算

这种方法使用了位运算和while循环来实现，而不是递归。这种方法通常被称为“二进制GCD算法”或“辗转相除法”的变种。此方法计算gcd的效率非常高效，但是一般人是不知道有这种方法，这里给大家介绍一下，供大家了解，其实真正用起来，基本所有的问题前两种都能够解决，大家根据自己爱好选择学习。

循环的条件是（m%=n）&&（n%=m）。这意味着只要m除以n的余数不为0，并且n除以m的余数也不为0，循环就会继续。在每次循环中，m和n都会更新为它们之间的余数。这个过程会不断重复，直到其中一个变为0，最后返回的是a+b，下面我们模拟一下过程。

最大公约数（GCD）模板：

int gcd(int m,int n){//辗转相除法return n==0?m:gcd(n,m%n);
}
int gcd(int m,int n){//三目运算符实现return n>0?gcd(n,m%n):m;
}
int gcd(int m,int n){//位运算，速度大于前两种while((m%=n)&&(n%=m));return m+n;
}

最大公约数（GCD）例题：

AcWing 4199. 公约数

给定两个正整数 a 和 b。

你需要回答 q 个询问。

每个询问给定两个整数 l,r，你需要找到最大的整数 x，满足：

1. x 是 a 和 b 的公约数。
2. l≤x≤r。

输入格式

第一行包含两个整数 a,b。

第二行包含一个整数 q。

接下来 q 行，每行包含两个整数 l,r。

输出格式

每个询问输出一行答案，即满足条件的最大的 x，如果询问无解，则输出 −1。

数据范围

前六个测试点满足 1≤a,b≤100，1≤q≤20。
所有测试点满足 1≤a,b≤10^9，1≤q≤10^4，1≤l≤r≤10^9。

输入样例：

9 27
3
1 5
10 11
9 11

输出样例：

3
-1
9

解题思路：

本题考察为最大公约数+二分查找，首先有了a,b，我们先求出这两个数的最大公约数，即所有的公约数都要小于这个数，那么我们再用试除法求这个最大公约数的因子，最大公约数的因子必然也能被a,b整除，比如12，8，最大公约数为4，4的因子为2，2也能被4整除。这样我们得到一个因子数组，在这个数组里面去查找满足条件的值，既然要二分查找那么就要对此数组进行排序。我们试除法时会产生很多重复的数，排完序这并不影响二分查找，无非是多查找几次，二分的效率是非常高的，无伤大雅。为社么满足nums[mid]<=r的才left=mid;按二分模板来说是l<=nums[mid]<=r，最后为什么还要再判断nums[left]<l||nums[left]>r，这里解释一下：

AC代码： 

#include<iostream>
#include<algorithm>
using namespace std;
int a,b,q,l,r;
int nums[10005];
int k;
int gcd(int m,int n){return n>0?gcd(n,m%n):m;
}
void fun(int tmp){//试除法求tmp所有因子nums[k++]=tmp;for(int i=1;i*i<=tmp;i++){//1-sqrt(tmp)范围if(tmp%i==0){//能够整除nums[k++]=i;//自己是因子nums[k++]=tmp/i;//另一个因子的也是}}
}
int main(){cin>>a>>b>>q;int maxgcd=gcd(b,a);//最大公约数fun(maxgcd);sort(nums,nums+k);//排序，有重复的数不用管while(q--){cin>>l>>r;if(l>maxgcd||r<1){//在给定的区间之外cout<<-1<<endl;}else{//二分法求满足条件的最大的公约数int left=0,right=k-1;while(left<right){int mid=left+right+1>>1;if(nums[mid]<=r){left=mid;}else{right=mid-1;}}if(nums[left]<l||nums[left]>r){//若找到的不在区间内cout<<-1<<endl;}else{cout<<nums[left]<<endl;}}}return 0;
}

---

最小公倍数（LCM）

两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。例如：8和12的最小公倍数为24，24%8=0且24%12=0，只要满足8*a=12*b=c，只要我们得到的c是最小的即可。

最小公倍数（LCM）求解：

最小公倍数（LCM）的求解就比较统一化了，没有最大公约数（GCD）的写法这么多了，一般绝大多数人都是使用m*n/gcd(m,n)，m*n是必然得到一个公倍数，这个公倍数不确定是不是最小的，我们再去用m与n的最大公约数与得到的公倍数做除法，即：m*n/gcd(m,n)，这样便可以得到最小公倍数（LCM），在实现此公式时，为了避免m*n会爆int，我们通常会先让一个数m/gcd（m,n)，再去乘n，最终得到m/gcd(m,n)*n。当然你也可以开的大一点long long、int long long。当m/gcd（m,n)时必然得到一个整数，因为gcd（m,n）是n与m的最大公约数（GCD）也是m的约数。

最小公倍数（LCM）模板：

int lcm(int m,int n){return m/gcd(m,n)*n;
}

最小公倍数（LCM）例题：

AcWing 3827. 最小正整数

给定两个整数 n 和 k。

请你计算，末尾至少有连续 k 个 0，并且可以被 n 整除的最小正整数。

例如，当 n=375,k=4 时，满足条件的最小正整数为 30000。

输入格式

第一行包含整数 T，表示共有 T 组测试数据。

每组数据占一行，包含两个整数 n,k。

输出格式

每组数据输出一行结果，表示满足条件的最小正整数。

数据范围

所有数据满足 1≤T≤10，1≤n≤109，0≤k≤8。

输入样例：

6
375 4
10000 1
38101 0
123456789 8
1 0
2 0

输出样例：

30000
10000
38101
12345678900000000
1
2

 解题思路：

这道题其实就是求两个数的最小公倍数，一个是n，另一个是1ek。末尾至少有连续 k 个 0，那么最小我们可以取到1ek，并且可以被 n 整除的最小正整数最终答案为lcm(n,1ek)，注意此题要开long long。

AC代码：

#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;//注意开long long
int T;
ll n,k;
ll gcd(int m,int n){//求gcdreturn n>0?gcd(n,m%n):m;
}
ll lcm(int m,int n){//求lcmreturn m/gcd(m,n)*n;
}
int main(){cin>>T;while(T--){cin>>n>>k;k=pow(10,k);//变为1ekcout<<lcm(n,k)<<endl;//求两个数的最小公倍数即可}return 0;
}

---

最大公约数（GCD）与最小公倍数（LCM）是算法之中最基础的部分，是每一位算法初学者的首选，也是数学之中必学的内容，博主以写此篇总结归纳GCD、LCM供大家参考学习，文章尚有不足，若有错误的地方恳请各位大佬指出。

执笔至此，感触彼多，全文将至，落笔为终，感谢大家的支持。