萌新的第一个帖子,别说我写的差了
别人随随便便一个帖子直接几十个赞,我这就2赞啊,很搞人心态的,求点赞
本帖禁止刷罐
如果我们想要求两数的最大公因数,平时我们可能是直接暴力,依次枚举进行判断,如下代码:
对于一些比较大的数据暴力就 TLE 了,这时候我们就要用辗转相处法
数学思维:对于要求 a和b( a≥b)的最大公因数辗转相除法步骤:k = b, b = a % b, a = k ……不断重复,直到b = 0时,k就是答案。
因此我们可以写出两种代码(迭代 和 递归):
1.迭代法
2.递归法
c++11有__gcd(a, b)可以直接求解!
拓展:我们可以通过求最大公因数来求最小公倍数:A * B / 最大公因数(不懂看最下面)
可以写出代码:
在c++17有直接求解最大公因数的函数lcm(a, b)
附件:为什么最小公倍数 = 乘积 / 最大公因数?
令a === 最大公因数 * (a / 最大公因数) b === 最大公因数 * (b / 最大公因数)
则其最小公倍数 = 最大公因数(公共的,只用乘一次) * (a /// 最大公因数) * (b /// 最大公因数) = a ∗*∗ b /// 最大公因数
辗转相除法证明过程:
设 a = q × b + r,其中 q 是 a 除以 b 的商,r 是余数(0 ≤ r < b)。
第一步:证明 gcd(a, b) 是 b 和 r 的公因数
令 d = gcd(a, b),则 d 能整除 a,也能整除 b。
由 r = a - q × b,因为 d 能整除 a 和 b,所以 d 也能整除 r。
因此 d 是 b 和 r 的公因数,所以 d ≤ gcd(b, r)。
第二步:证明 gcd(b, r) 是 a 和 b 的公因数
令 e = gcd(b, r),则 e 能整除 b,也能整除 r。
由 a = q × b + r,因为 e 能整除 b 和 r,所以 e 也能整除 a。
因此 e 是 a 和 b 的公因数,所以 e ≤ gcd(a, b)。
由第一步和第二步可得:d = e
即:gcd(a, b) = gcd(b, a mod b)
结论:
反复使用这个等式,每次把较大的数换成它除以较小数的余数,不断重复,直到余数为 0。此时,那个非零的除数就是原来两个数的最大公因数。这就是辗转相除法(欧几里得算法)的原理。
求赞!!!