求最大公约数
可以用辗转相除法来求，基本思想：两个数的最大公约数等于两个数中较小的数与两数余数的最大公约数。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//n不能 = 0
int gcd(int m,int n)
{
int t = 1;
while(t != 0)
{
t=m%n;
m=n;
n=t;
}
return m;
}
// a和b不能 = 0
int gcd(ll a , ll b){
if(a < b){
ll t = a;
a = b;
b = t;
}
if(a % b){
gcd(b , a%b);
}
else return b;
}
正确性证明
我们设g为a和b的最大公约数，则a = mg , b = ng，其中，m和n互质。
证明算法的最终结果为a和b的一个公因子
a/b = f1 …….. c1
b/c1 = f2 ……….. c2
.
.
.
cn-1/cn = fn …….. 0
由上式可得：cn为最终结果，且 cn-1 = fn cn, cn-2 = fn-1 cn-1 + cn, 同理可得，a和b均可以被cn整除，所以cn为a和b的一个公因子，所以 cn <= g
证明cn为最大的公因子
由于a = mg = f1 b + c1 = f1 n g + c1, 所以 (m - f1 n) g = c1, 又因为(m - f1 * n) >=1 ，所以 g <= c1，同理，g <= cn，而cn <= g，所以cn = g。
求最小公倍数
a和b的最小共倍数 = a * b / gcd(a , b)