最大公约数
最大公约数(GCD)是两个或多个整数的所有公约数中最大的一个
一般用 gcd(a,b) 来表示 a 和 b 的最大公约数
常用辗转相除法(也称为欧几里得算法)来计算两个数的最大公约数
欧几里得算法
对于整数 a和 b,它们的最大公约数与 b 和(a 除以 b 的余数)c 的最大公约数相等。即 gcd(a, b) = gcd(b, a % b).通过不断迭代,直到余数为 0,此时的除数即为最大公约数。
定理的证明
辗转相除法的原理基于以下定理
设a、b均为正整数,则$$gcd(a,b)=gcd(b,a \% b)$$
证明:
假设d是a和b的一个公约数,那么d可以整除a和b。
由于r是a除以b的余数,因此a可以表示为a = bq + r,其中q是商,r是余数。
由于d可以整除a和b,那么d也可以整除bq,因此d也可以整除r(因为r = a - bq)。所以,d也是b和r的一个公约数。
反过来,假设e是b和r的一个公约数,那么e可以整除b和r。
由于a = bq + r,e也可以整除a(因为e可以整除bq和r,所以e也可以整除它们的和a)。所以,e也是a和b的一个公约数。
因此,a和b的公约数集合与b和r的公约数集合是相同的。所以,它们的最大公约数也是相同的,即gcd(a, b) = gcd(b, r)。
求最大公约数
通过上面的定理可以发现,
- 如果 $a<b$,那么定理的结果就是将a和b交换
- 如果 $a>b$,那么通过这个定理总可以将数据规模变小,并且减小的非常快。
现在还需要一个递归边界,数据规模减小到什么程度才能算出结果呢?
因为,0和任意一个整数a的最大公约数都是a,所以,当其中一个数为0时,到达边界,另一个数就是最大公约数。
递归的两个关键
① 递归式:$gcd(a,b)=gcd(b,a \% b)$
② 递归边界:$gcd(a,0)=a$
代码
写法一
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
写法二
int gcd(int a, int b) {
return !b ? a : gcd(b, a % b);
}
最小公倍数
最小公倍数是指所有公倍数中最小的那个公倍数。
一般用 lcm(a,b) 来表示 a 和 b 的最小公倍数
求最小公倍数
最小公倍数是在最大公约数的基础上进行的。当得到 a 和 b 的最大公约数 d 之后,可以马上得到 a 和 b 的最小公倍数是$$lcm(a,b)=a\times b /gcd(a,b)$$
注意:
由于 $a\times b$ 在实际计算时有可能溢出,因此,更恰当的写法是
$$a/gcd(a,b)\times b$$
代码
int lcm(int a, int b) {
return (a / gcd(a, b)) * b;
}