本文主要是介绍最大公约数、最小公倍数【模板】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
最大公约数、最小公倍数性质：
1.若a | m，b | m，则lcm(a，b) | m。
2.若d | a，d | b，则d | gcd(a，b)。
3.lcm(a，b) = a * b / gcd(a，b)。
4.设m，a，b是正整数，则lcm(m*a，m*b) = m * gcd(a，b)
5.若m是非零整数a1，a2，…，an的公倍数，则lcm(a1，a2，…，an) | m。
用素因子分解法求a和b的最大公约数和最小公倍数：
a = p1^r1 * p2^r2 * … * pk^rk
b = p1^s1 * p2*s2 * … * pk^sk
gcd(a，b) = p1^min(r1,s1) * p2^min(r2,s2) * … * pk^min(rk,sk)
lcm(a，b) = p1^max(r1,s1) * p2^max(r2,s2) * … * pk^max(rk,sk)
最大公约数：
欧几里得算法O(n)
int GCD(int a,int b)
{if(a < b)int temp = a, a = b, b = temp;if(b == 0) return a;return GCD(b,a%b);
}Stein算法O( log(max(a,b)) )
int KGCD(int a,int b)
{if(a == 0) return b;if(b == 0) return a;if(~a & 1){if(b & 1) return KGCD(a>>1, b);else return KGCD(a>>1, b>>1) << 1;}if(~b & 1) return KGCD(a, b>>1);if(a > b) return KGCD((a-b)>>1, b);return KGCD((b-a)>>1, a);
}
最小公倍数：
int LCM(int a,int b)
{return a/KGCD(a,b)*b;
}欧几里得算法O(n)实现原理：
设两数为a、b(a>b），求a和b最大公约数(a，b）的步骤如下：
用b除a，得a÷b=q......r1(0≤r1）。若r1=0，则（a，b)=b；
若r1≠0，则再用r1除b，得b÷r1=q......r2 (0≤r2）.
若r2=0，则（a，b)=r1，若r2≠0，则继续用r2除r1，……
如此下去，直到能整除为止。其最后一个非零除数即为（a，b）。
stein算法O( log(max(a,b)) )实现原理：
gcd(a,a)=a，也就是一个数和其自身的公约数仍是其自身。gcd(ka,kb)=k gcd(a,b)，也就是最大
公约数运算和倍乘运算可以交换。特殊地，当k=2时，说明两个偶数的最大公约数必然能被2整除。
当k与b互为质数，gcd(ka,b)=gcd(a,b)，也就是约掉两个数中只有其中一个含有的因子不影响最
大公约数。特殊地，当k=2时，说明计算一个偶数和一个奇数的最大公约数时，可以先将偶数除以
2。
算法过程：
1、如果An=Bn,那么An(或Bn)*Cn是最大公约数,算法结束
2、如果An=0，Bn是最大公约数，算法结束
3、如果Bn=0，An是最大公约数，算法结束
4、设置A1=A、B1=B和C1=1
5、如果An和Bn都是偶数，则An+1=An/2，Bn+1=Bn/2，Cn+1=Cn*2(注意，乘2只要把整数左移一位
即可，除2只要把整数右移一位即可)
6、如果An是偶数，Bn不是偶数，则An+1=An/2，Bn+1=Bn，Cn+1=Cn(很显然啦，2不是奇数的约数)
7、如果Bn是偶数，An不是偶数，则Bn+1=Bn/2，An+1=An，Cn+1=Cn(很显然啦，2不是奇数的约数)
8、如果An和Bn都不是偶数，则An+1=|An-Bn|/2，Bn+1=min(An,Bn)，Cn+1=Cn
9、n加1，转1
这篇关于最大公约数、最小公倍数【模板】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
