辗转相除法

liudonghao · 2023-05-16 10:37:53 · 个人记录

前言

对于两个整数 a,b 且 b\ne 0，一定有 a=bq+r (0\le r <|b|) 。其中，q 叫做 a 除以 b 的商；r 叫做 a 除以 b 的余数，记作 a\bmod{b} 。

若 r=0 , 则称 a 被 b 整除，记作 b|a 。

设 a,b,\cdots ,c 不全为 0 , 同时整除他们所有的整数称为它们的公约数，其中最大的一个称为 a,b,\cdots ,c 的最大公约数，用 (a,b,\cdots ,c) 表示。

正文

辗转相除法又名欧几里得算法，是求得 (a,b) 的一种方法。

算法核心思想 : (a , b)=(b,a \bmod b) (a>b)

证明：

设 a=bq+r(0\le r<|b|) ，d 为 a 和 b 的一个公约数。

两边同时除以 d 得：

因此，a 和 b 所有的公约数一定是 r 的约数

所以 a 和 b 的公约数一定也是 b 和 r 的公约数

所以，(a,b)=(b,a\bmod b)

证毕。

算法可用递归函数实现，时间复杂度为 O(\log_2 max(a,b))

代码：

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

更简洁的代码：

int gcd(int a,int b)
{
    return b ? gcd(b,a % b) : a;
}