最大公约数

最大公约数

概念

设 a 和 b 是 2 个不为 0 整数，如果 d∣a 且 d∣b，则称 d 是 a 与 b 的公约数。而 a,b 的所有公约数中最大的被称为 a,b 的最大公约数，记作 gcd(a,b)

最小公倍数

概念

设 a 和 b 是 2 个不为 0 整数，如果 a∣d 且 b∣d，则称 d 是 a 与 b 的公倍数。而 a,b 的所有公倍数中最小的被称为 a,b的最小公倍数，记作 lcm(a,b)

gcd 和 lcm 的性质

1. 若 a∣m，b∣m，则 gcd(a,b)∣m
2. 若 d∣a，d∣b，则 d∣lcm(a,b)
3. lcm(a, b) = <math> <semantics> <mrow> <mfrac> <mrow> <mi> a </mi> <mi> b </mi> </mrow> <mrow> <mi> g </mi> <mi> c </mi> <mi> d </mi> <mo> ( </mo> <mi> a </mi> <mo separator="true"> , </mo> <mi> b </mi> <mo> ) </mo> </mrow> </mfrac> </mrow> <annotation encoding="application&#47;x&#45;tex"> \frac{ab}{gcd(a, b)} </annotation> </semantics> </math>gcd(a,b)ab​
4. 设 m,a,b 是正整数，则 lcm(ma,mb)=m×lcm(a,b)
5. 若 m 是非零整数 $a_1,a_2,a_3,…,a_n $ 的公倍数，则 <math> <semantics> <mrow> <mi> l </mi> <mi> c </mi> <mi> m </mi> <mo> ( </mo> <msub> <mi> a </mi> <mn> 1 </mn> </msub> <mo separator="true"> , </mo> <msub> <mi> a </mi> <mn> 2 </mn> </msub> <mo separator="true"> , </mo> <mi mathvariant="normal"> . </mi> <mi mathvariant="normal"> . </mi> <mi mathvariant="normal"> . </mi> <mo separator="true"> , </mo> <msub> <mi> a </mi> <mi> n </mi> </msub> <mo> ) </mo> <mo> ∣ </mo> <mi> m </mi> </mrow> <annotation encoding="application&#47;x&#45;tex"> lcm(a_1,a_2,...,a_n) \mid m </annotation> </semantics> </math>lcm(a1​,a2​,...,an​)∣m

欧几里得算法

欧几里得算法又称为辗转相除法。该算法用来快速计算 2 个整数的最大公约数。

欧几里得算法的原理就是一个公式： <math> <semantics> <mrow> <mi> g </mi> <mi> c </mi> <mi> d </mi> <mo> ( </mo> <mi> a </mi> <mo separator="true"> , </mo> <mi> b </mi> <mo> ) </mo> <mo> = </mo> <mi> g </mi> <mi> c </mi> <mi> d </mi> <mo> ( </mo> <mi> b </mi> <mo separator="true"> , </mo> <mi> a </mi> <mtext>   </mtext> <mrow> <mi mathvariant="normal"> m </mi> <mi mathvariant="normal"> o </mi> <mi mathvariant="normal"> d </mi> </mrow> <mtext>   </mtext> <mi> b </mi> <mo> ) </mo> </mrow> <annotation encoding="application&#47;x&#45;tex"> gcd(a, b) = gcd(b, a\ \mathrm{mod}\ b) </annotation> </semantics> </math>gcd(a,b)=gcd(b,a mod b)

证明：设 a=qb+r，其中 a,b,q,r 都是整数，我们只需证明 gcd(a,b)=gcd(b,r)。设 d 是 a 与 b 的公约数，即 d∣a 且 d∣b。注意到 r=a−qb，根据整除的性质，d∣a−qb，即 d∣r。所以对于任意 (a,b) 的公约数，都是 (b,r) 的公约数，故 (a,b) 的最大公约数等于 (b,r)最大公约数，即 gcd(a,b)=gcd(b,r)

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a%b);
}

我们借助递归来实现欧几里得算法，算法效率很高，时间复杂度可以认为是 O(lgN)，可以证明其递归层数不会超过 4.7851lgN+1.6723，其中 N = max(a,b)

返回目录，查看更多