给出两个数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
代码如下，非常简单，一行就够了：
int GCD(int a,int b)
{
return a%b?GCD(b,a%b):b;
}
二、最小公倍数(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)
设两个数分别为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)
代码如下：
#include <iostream>
using namespace std;
int GCD(int a,int b)
{
return a%b?gcd(b,a%b):b;
}
int main()
{ int i,n,m,temp=,ans=;
cin >> n;
for (i=; i<=n; i++)
{
temp=GCD(ans,i);
ans=ans*i /temp;
}
cout << ans << '\n'; return ;
}