更相减损术（辗转相减法）

sunset_breeze · 2024-01-01 08:56:55 · 个人记录

更相减损术：已知两数a和b，求gcd(a,b)。

不妨设a \geq b，若a=b，则gcd(a,b)=a=b，否则对于所有\forall d|a,d|b，可以证明d|a-b。

证明d|a-b如下，设a=k_1\times d，b=k_2 \times d，因为a>b，所以一定有(k_1>k_2)。所以a-b=(k_1-k_2)\times d，又因为k_1\neq k_2，所以d|a-b，故得证。

因此，a和b的所有公因数都是a-b和b的公因数，即gcd(a,b)=gcd(b,a-b)。

算法优化

如果a >> b(>>表示远大于)，那么这个算法时间复杂度是O(|a|)的。

那考虑优化，若2|a,2|b，gcd(a,b)=2\times gcd(\frac{a}{2},\frac{b}{2})，否则若2|a,2\nmid b（2|b）同理，gcd(a,b)=\frac{a}{2},b，再如果2 \nmid a,2 \nmid b时，那么一定2|a-b，那么又回到2|a,2\nmid b的情况了，优化后的算法是O(log~n)的。

证明如下，每次操作一定至少能将a和b之一减半。否则2|a-b，回到上一种情况，算法最多进行O(log~n)次。