• 欢迎光临~

# 最大公约数

## 辗转相除

``````int gcd(int a, int b) {
if (!b || a == b) return a;
if (a > b) return gcd(b, a % b);
else return gcd(a, b % a);
}
``````

## 更相减损术

``````int gcd(int a, int b) {
if (a == b) return a;
if (a > b) return gcd(b, a - b);
else return gcd(a, b - a);
}
``````

## 辗转相除结合更相减损术

a偶b偶，\$gcd(a,b) = 2gcd(a/2, b/2) = 2gcd(a>>1, b>>1)\$

a偶b奇，\$gcd(a,b) = gcd(a/2, b) = gcd(a>>1, b)\$

a奇b偶，\$gcd(a,b) = gcd(a, b/2) = gcd(a, b>>1)\$

a奇b奇，利用更相减损术运算一次，\$gcd(a,b) = gcd(b, a-b)\$， 此时a-b必然是偶数，又可以继续进行移位运算。

``````int gcd(int a, int b) {
if (a == b) return a;
if (a & 1) {
if (b && 1) return gcd(a, std::abs(a - b));
else return gcd(a, b >> 1);
}
else {
if (b & 1) return gcd(a >> 1, b);
else return 2 * gcd(a >> 1, b >> 1);
}
}
``````

## 参考

https://houbb.github.io/2017/08/23/math-03-common-gcd-03

https://zhuanlan.zhihu.com/p/31824895

# 最小公倍数

``````a * b / gcd(a, b)
``````

# 扩展欧几里得

## 原理

\$\$
a x_1 + b y_1 = gcd(a, b) tag{1}
\$\$

\$\$
bx_2 + (a % b) y_2 = gcd (b, a % b) tag{2}
\$\$

\$\$
begin{align}
gcd(a, b) &= gcd (b, a % b) tag{3}
a % b &= a - lfloor frac{a}{b} rfloor b tag{4}
end{align}
\$\$

\$\$
a y_2 + b left [ x_2 - lfloor frac{a}{b} rfloor y_2 right ] = gcd (a, b) tag{5}
\$\$

\$\$
begin{align}
x_1 &= y_2
y_1 &= x_2 - lfloor frac{a}{b} rfloor y_2
end{align}
\$\$

``````int exgcd(int a,int b,int &x,int &y)
{
if (b==0) {
x = 1;
y = 0;
return a;
}
int r = exgcd(b, a%b, x, y);
int t = y;
y = x - (a / b) * y;     //2的情况
x = t;
return r;
}
``````

## 通解

\$\$
begin{align}
x &= x_0 + frac{b}{c} k
y &= y_0 - frac{a}{c} k
end{align}
\$\$

\$\$
a x + b y = a left( x_0 + frac{b}{c} k right) + b left( y_0 - frac{a}{c} k right) = a x_0 + b y_0 = c
\$\$

## 参考

https://zhuanlan.zhihu.com/p/100567253

https://zhuanlan.zhihu.com/p/42707457

https://www.desgard.com/algo/docs/part2/ch02/3-ext-euclidean/

https://ksmeow.moe/euclid/

https://www.cnblogs.com/wkfvawl/p/9350867.html

## 例子

``````#include <cstdio>
using namespace std;

int exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return a;
}
int gcd = exgcd(b, a % b, x, y), temp = y;
y = x - a / b * y;
x = temp;
return gcd;
}
int main() {
int a, b, x, y;
scanf("%d%d", &a, &b);
exgcd(a, b, x, y);
printf("%dn", (x % b + b) % b);
return 0;
}
``````

• Leetcode365 水壶问题