扩展欧几里得
地铁dixiatielu
2019-09-10 16:32:42
最大公约数的定理
$a*b/gcd(a,b) = lcm(a,b)$
```cpp
a * b / __gcd(a,b) = lcm(a,b);
```
## 扩展欧几里得板子如下
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
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 temp=y; //把x y变成上一层的
y=x-(a/b)*y;
x=temp;
return r; //得到a b的最大公因数
}
```