gcd与lcm求解与题目

gcd 最大公约数

因子、约数、最大公约数等中学时期已经学过，再次不过多赘叙。

几个关于gcd的定理：

gcd(n,n+1)=1；

如果a=qb+r，其中aqbr都为整数，则gcd(a,b)=gcd(b,r)；

如果gcd(a,b)=1，则a和b互素。

gcd有几种求法，在此只列举三种。

方法一：引用gcd函数（慢）

#include<algorithm>
int gcd(int a,int b){
    return __gcd(a,b);//此处有两个_
}

方法二：辗转相除法（中）（也叫欧几里得算法）

int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}

方法三：位运算（快）

int gcd(int a,int b) 
{    
    while(b^=a^=b^=a%=b);    
    return a;
}

三种求法皆可以求gcd，但使用时需要注意a,b是否为0；

最小公倍数的基本概念已在中学时期教授过，在此直接跳过。

下面只展示一种基于数学定理的求法，若a*b溢出，可更改运算顺序来保证答案准确。

int lcm(int a,int b){
    return a*b/gcd(a,b);
}

上述gcd与lcm的数据范围皆为int，可根据题意更改为long long等。

并且，0没有最大公约数。