Gcd

▪ 欧几里得算法又称辗转相除法，用于计算两个正整数 a， b 的最大公约数。

▪ 计算公式为 gcd(a,b) = gcd(b,a mod b)。

▪ 公式无需证明，记忆即可。

▪ 如果要求多个数的最大公约数。易证，每次取出两个数再放回去，不会影响答案正

确性。

▪ 比如 a,b,c 三个数，答案就是 gcd(gcd(a,b),c)

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

 

 

扩展 Gcd

▪ 求出 ax + by = gcd(a,b)的一组可行解。

 

 

 

void exgcd(int a,int b,int& d,int& x,int& y){    if(!b)    {        d=a;                x=1;                y=0;    }    else    {        exgcd(b,a%b,d,y,x);        y-=x*(a/b);    }}

 

 

LCM 最小公倍数

▪ lcm(m,n) = (m * n) / gcd(m,n)

▪ 我们使用刚刚的欧几里得算法求出 gcd 后，即可求得 lcm。

▪ 如果要求解多个数的最小公倍数,则做法与 gcd 类似。

▪ 比如有 a,b,c 三个数,答案就是 lcm(lcm(a,b),c)