给出两个数a、b，求最大公约数(GCD)与最小公倍数(LCM)

一、最大公约数(GCD)

　   最大公约数的递归：

 * 1、若a可以整除b，则最大公约数是b

 * 2、如果1不成立，最大公约数便是b与a%b的最大公约数

 * 示例：求(140,21)

 * 140%21 = 14

 * 21%14 = 7

 * 14%7 = 0

 * 返回7

　　代码如下，非常简单，一行就够了：

1 int GCD(int a,int b)2 {3     return a%b?GCD(b,a%b):b;4 }

 二、最小公倍数(LCM)

　　求出最大公约数后m后，最小公倍数就是a*b/m了，很简单。这里做一个扩展，求1~n共n个数的最小公倍数

思路：

两个数的情况:

设两个数分别为a,b

先用辗转相除法求gcd(a,b)，也就是a,b的最大公约数

然后lcm(a,b)=a*b/gcd(a,b)

n个数的情况:

设n个数分别为a1,a2,……an

则先求b1=lcm(a1,a2)

再求b2=lcm(b1,a3)

b3=lcm(b2,a4)

b4=lcm(b3,a5)

……

最后求到b[n-1]就是答案

复杂度接近O(n)

代码如下：

1 #include 
       
         2 using namespace std; 3 int GCD(int a,int b) 4 { 5     return a%b?gcd(b,a%b):b; 6 } 7 int main() 8 {    9     10     int i,n,m,temp=0,ans=1;       11     cin >> n;        12 　　 for (i=1; i<=n; i++) 13 　　 {                       14     　　temp=GCD(ans,i);           15     　　ans=ans*i /temp;16 　 　}       17 　　cout << ans << '\n';   18   19 return 0;20 }