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

也称为最大公因数或最大公因子，是指两个或多个整数共有的约数中最大的一个。在数学中，这是指能够同时被这些整数整除的最大的正整数。例如，8与12的最大公约数为4，4同时能够被8与12整除，找不到x>4同时满足8%x=0且12%x=0这样的数，我们就认为4是8与12的最大公约数（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，下面我们模拟一下过程。

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;
}

给定两个正整数 a 和 b。

你需要回答 q 个询问。

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

x 是 a 和 b 的公约数。

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

本题考察为最大公约数+二分查找，首先有了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，这里解释一下：

#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;
}

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

最小公倍数（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的约数。

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

给定两个整数 n 和 k。

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

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

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

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

所有数据满足 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。

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

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

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