欧几里得算法 欧几里得算法又称为辗转相除法，是为了计算两个数的最大公约数。
定理： g c d ( a , b ) = g c d ( b , a m o d
b ) ( a >
b ) gcd(a, b) = gcd(b, a\mod b ) (a>
b) gcd(a,b)=gcd(b,amodb)(a>b)
证明：假设 a >
b a >
b a>b，a 可以表示为 a = k ? b + r a = k*b+r a=k?b+r，则 r = a m o d
b r = a\mod b r=amodb
1.对于充分性，假设 d 是 a，b的一个公约数，即 d = g c d ( a , b ) d = gcd(a, b) d=gcd(a,b)，则有 a ∣ d , b ∣ d a\mid d, b \mid d a∣d,b∣d，（a和b都能被d整除），而 r = a ? k ? b r = a- k* b r=a?k?b，因此 r ∣ d r\mid d r∣d。即 d = g c d ( b , r ) d = gcd(b, r) d=gcd(b,r)
2.对于必要性：假设d是 g c d ( b , a m o d
b ) gcd(b, a\mod b) gcd(b,amodb)的公约数，即 b ∣ d , r ∣ d b\mid d, r\mid d b∣d,r∣d，同样，因为 a = k ? b + r a = k*b+r a=k?b+r，则： a ∣ d a\mid d a∣d，即 d = g c d ( a , b ) d = gcd(a, b) d=gcd(a,b)
由上可知， g c d ( a , b ) gcd(a, b) gcd(a,b) 与g c d ( b , a m o d
b ) gcd(b, a\mod b) gcd(b,amodb)的公约数相等，则其最大公约数也相等。
辗转相除到最后， g c d ( x , 0 ) = x gcd(x, 0) = x gcd(x,0)=x。
代码：
int gcd(int a, int b)
{
if(b == 0)
return a;
returngcd(b, a % b);
}int gcd(int a,int b)
{
int r;
while(b!=0)
{
r=a%b;
//当a扩展欧几里得 扩展欧几里德算法是用来在已知a, b求解一组x，y，使它们满足贝祖等式：a x + b y = g c d ( a , b ) = d ax+by = gcd(a, b) =d ax+by=gcd(a,b)=d（解一定存在，根据数论中的相关定理）。扩展欧几里德常用在求解模线性方程及方程组中。
解 x，y的方法：
- 显然当b = 0 ， g c d （ a ， b ） = a b=0，gcd（a，b）=a b=0，gcd（a，b）=a。此时x = 1 ， y = 0 x=1，y=0 x=1，y=0；
也就是 1 ? a + 0 ? b = a 1*a+0*b = a 1?a+0?b=a
- 设a x 1 + b y 1 = g c d ( a , b ) ax1+by1=gcd(a,b) ax1+by1=gcd(a,b);
在下一个exgcd里b x 2 + ( a m o d b ) y 2 = g c d ( b , a m o d b ) bx2+(a mod b)y2=gcd(b,a mod b) bx2+(amodb)y2=gcd(b,amodb);
根据欧几里德原理有 gcd(a,b)=gcd(b,a mod b);
则: a x 1 + b y 1 = b x 2 + ( a m o d b ) y 2 ax1+by1=bx2+(a mod b)y2 ax1+by1=bx2+(amodb)y2;
即: a x 1 + b y 1 = b x 2 + ( a ? ( a / b ) ? b ) y 2 = a y 2 + b x 2 ? ( a / b ) ? b y 2 ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2 ax1+by1=bx2+(a?(a/b)?b)y2=ay2+bx2?(a/b)?by2;
根据恒等定理得：x1=y2; y1=x2-(a/b)*y2;
这样我们就得到解 x1,y1 的方法：x1，y1 的值基于 x2，y2。
怎样求出最小整数解x呢？
a x + b y = c ax + by = c ax+by=c其实就等价于 a x ≡ c ( m o d b ) ax ≡ c (mod b) ax≡c(modb)，当存在一个特解 x 1 x1 x1使得 a x 1 + b y 1 = c ax1+by1=c ax1+by1=c。那么 x 1 x1 x1加上若干倍 b b b还是这个方程的解，即 x = x 1 + k ? b x=x1+k*b x=x1+k?b仍为方程的解。此时： y = y 1 ? k ? a y=y1-k*a y=y1?k?a.因而方程在 [ 0 , b ? 1 ] [0, b-1] [0,b?1]上一定有整数解（假如小于0，你加上若干倍b啊，就可以让它保持在 0 0 0 ~b ? 1 b-1 b?1中；如果大于b-1，你减去若干倍b啊，它也保持0~b-1）。(即 x = ( x % t + t ) % t x=(x\%t+t)\%t x=(x%t+t)%t)
代码：
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 r = exgcd(b, a % b, y, x);
int t = x;
//y -= x*(a/b);
x = y;
y = t - (a / b) * y;
return r;
}
扩展欧几里得求逆元 【模板_总结|扩展欧几里得算法(推导，逆元）】若 m x ≡ 1 m o d n mx≡1 mod n mx≡1modn, 则称m关于1模n的乘法逆元为x。也可表示为mx≡1(mod n)。逆元相当于数论中的倒数。
条件：只有当 g c d ( m , n ) = 1 gcd(m, n) = 1 gcd(m,n)=1，m才有关于模n的逆元。
- 利用费马小定理 a ? a p ? 2 ≡ 1 ( m o d p ) a\cdot a^{p-2}\equiv1(\mod p) a?ap?2≡1(modp)， a p ? 2 a^{p-2} ap?2即为a关于模p的逆元，但只能求出p为素数的情况下的乘法逆元。
- 采用扩展欧几里德算法来计算普遍情况下的乘法逆元的情况。
由 m x ≡ 1 m o d n mx≡1 mod n mx≡1modn，可以推出 m x ? k n = 1 mx-kn=1 mx?kn=1，与 a x + b y = g c d ( a , b ) = 1 ax+by=gcd(a, b)=1 ax+by=gcd(a,b)=1，相比较即可得出，令 a = m , b = n a = m,b = n a=m,b=n，所求出x即为逆元，加上 x = ( x % t + t ) % t x=(x\%t+t)\%t x=(x%t+t)%t即为最小逆元。
#include
#define INF 0x3f3f3f3f
#define d(x) cout << (x) << endl
#pragma GCC diagnostic error "-std=c++11"
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if(b == 0){
x = 1;
y = 0;
return a;
}
ll r = exgcd(b, a % b, y, x);
y -= x * (a / b);
return r;
}
int main()
{
ll m, n;
cin >> m >> n;
ll a, b, x, y;
a = m;
b = n;
ll gcd = exgcd(a, b, x, y);
cout << (x % b + b) % b << endl;
return 0;
}
