最大公约数即为 Greatest Common Divisor,常缩写为 gcd。
一组整数的公约数,是指同时是这组数中每一个数的约数的数。
一组整数的最大公约数,是指所有公约数里面最大的一个。
那么如何求最大公约数呢?我们先考虑两个数的情况。
如果我们已知两个数 \(a\) 和 \(b\),如何求出二者的最大公约数呢?
不妨设\(a > b\)
我们发现如果 b 是 a 的约数,那么 b 就是二者的最大公约数。 下面讨论不能整除的情况,即\(a = b * q + r\),
其中\(r < b\)
我们通过证明可以得到\(gcd(a, b) = gcd(b, amodb)\),过程如下:
设 \(a=bk+c\),显然有 \(c=a \bmod b\)。设 \(d \mid a\),\(~d \mid b\),则\(c=a-bk\), \(\frac{c}{d}=\frac{a}{d}-\frac{b}{d}k\)。
由右边的式子可知\(\frac{c}{d}\) 为整数,即 \(d \mid c\),所以对于 \(a\),\(b\) 的公约数,它也会是 \(b\),\(a \bmod b\) 的公约数。
反过来也需要证明:
设 \(d \mid b\),\(~d\mid (a \bmod b)\),我们还是可以像之前一样得到以下式子
\(\frac{a\bmod b}{d}=\frac{a}{d}-\frac{b}{d}k,~\frac{a\bmod b}{d}+\frac{b}{d}k=\frac{a}{d}\)。
因为左边式子显然为整数,所以\(\frac{a}{d}\) 也为整数,即 d \mid a,所以 b,a\bmod b 的公约数也是 a,b 的公约数。
既然两式公约数都是相同的,那么最大公约数也会相同。
所以得到式子\(gcd(a, b) = gcd(b, amodb)\)
既然得到了 \(\gcd(a, b) = \gcd(b, r)\),这里两个数的大小是不会增大的,那么我们也就得到了关于两个数的最大公约数的一个递归求法。
int gcd(int a, int b) {
if(b == 0) return a;
return gcd(b, a % b);
}
int gcd(int a, int b) {
if(b == 0) return a;
return gcd(b, a % b);
}
int lcm = a * b / gcd(a, b);
手机扫一扫
移动阅读更方便
你可能感兴趣的文章