信息学竞赛中常说的欧几里德算法及拓展欧几里德算法是什么？
在学习信息学数论部分知识点的过程中，有两个比较重要的算法，那就是欧几里得算法与扩展欧几里得算法。
今天，我们就带大家一起来了解一下这两个算法，看起来相似的算法到底分别是解决了什么问题呢？
欧几里得算法
在学习一种算法前，我认为我们首先应该知道，这种算法是要解决什么问题的。
小学就已经学过了两个数的最大公约数，而欧几里得算法就是为了求出两个数a、b的最大公约数的，这个最大公约数可以表示为gcd(a,b)。
欧几里得算法又称辗转相除法，这个名字已经揭示了它的主要思想：
欧几里德算法的思想基于辗转相除法的原理，辗转相除法是欧几里德算法的核心思想，欧几里德算法说白了其实就是辗转相除法的计算机算法的实现而已。下面我们先说说辗转相除法，辗转相除法的内容：如果用gcd(a,b)来表示a和b的最大公约数，那么根据辗转相除法的原理，有gcd(a,b)=gcd(b,a mod (b))，其中mod()表示模运算，并且不妨让a>b,这样方便于模运算。
引理：gcd(a,b)=gcd(b,a%b)
证明：
设 r=a%b , c=gcd(a,b)
则 a=xc , b=yc , 其中x , y互质
r=a%b=a-pb=xc-pyc=(x-py)c
而b=yc
可知：y 与 x-py 互质
证明：
假设 y 与 x-py 不互质
设 y=nk , x-py=mk , 且 k>1 （因为互质）
将 y 带入可得
x-pnk=mk
x=(pn+m)k
则 a=xc=(pn+m)kc , b=yc=nkc
那么此时 a 与 b 的最大公约数为 kc 不为 k
与原命题矛盾，则 y 与 x-py 互质
因为 y 与 x-py 互质，所以 r 与 b 的最大公约数为 c
即 gcd(b,r)=c=gcd(a,b)
得证
当a%b=0时，gcd(a,b)=b
这样我们可以写成递归形式
它的函数代码只有一行，简单便捷，复杂度O(log n)：
代码
int gcd(int a,int b)//欧几里得算法 时间复杂度：O(logn)
{
if(!b) return a;
else return gcd(b,a%b);
}
int gcd(int a,int b)//简化版欧几里得算法 时间复杂度：O(logn)
{
return b?gcd(b,a%b):a;//一行代码就是爽
}
拓展欧几里得算法
换句话说，如果ax+by=m有解，那么m一定是gcd(a,b)的若干倍。（可以来判断一个这样的式子有没有解）
有一个直接的应用就是 如果ax+by=1有解，那么gcd(a,b)=1；
要求出这个最大公因数gcd(a,b)，我们最容易想到的就是古老悠久而又相当强大的欧几里得算法：
但是，对于上面的式子ax+by=m来说，我们并不仅仅想要知道有没有解，而是想要知道在有解的情况下这个解到底是多少。
所以，扩展欧几里得
当到达递归边界的时候，b==0，a=gcd(a,b) 这时可以观察出来这个式子的一个解：a*1+b*0=gcd(a,b)，x=1,y=0，注意这时的a和b已经不是最开始的那个a和b了，所以我们如果想要求出解x和y，就要回到最开始的模样。
初步想法：由于是递归的算法，如果我们知道了这一层和上一层的关系，一层一层推下去，就可以推到最开始的。类似数学上的数学归纳法。
假设当前我们在求的时a和b的最大公约数，而我们已经求出了下一个状态：b和a%b的最大公因数，并且求出了一组x1和y1使得 b*x1+(a%b)*y1=gcd
（注意在递归算法中，永远都是先得到下面一个状态的值）
这时我们可以试着去寻找这两个相邻状态的关系：
首先我们知道：a%b=a-(a/b)*b；带入：
b*x1 + (a-(a/b)*b)*y1
= b*x1 + a*y1 – (a/b)*b*y1
= a*y1 + b*(x1 – a/b*y1) = gcd 发现 x = y1 , y = x1 – a/b*y1
这样我们就得到了每两个相邻状态的x和y的转化，就可以在求gcd的同时对x和y进行求值了。
代码
#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的最大公因数
}
1、乘法逆元
对于缩系中的元素，每个数a均有唯一的与之对应的乘法逆元x，使得ax≡1(mod n)
一个数有逆元的充分必要条件是gcd(a,n)=1，此时逆元唯一存在
逆元的含义：模n意义下，1个数a如果有逆元x，那么除以a相当于乘以x。
扩展欧几里得解法：
给定模数m，求a的逆相当于求解ax=1(mod m)
这个方程可以转化为ax-my=1
然后套用求二元一次方程的方法，用扩展欧几里得算法求得一组x0,y0和gcd
检查gcd是否为1
gcd不为1则说明逆元不存在
若为1，则调整x0到0~m-1的范围中即可
代码
typedef long long ll;
void extgcd(ll a,ll b,ll& d,ll& x,ll& y){
if(!b){ d=a; x=1; y=0;}
else{ extgcd(b,a%b,d,y,x); y-=x*(a/b); }
}
ll inverse(ll a,ll n){
ll d,x,y;
extgcd(a,n,d,x,y);
return d==1?(x+n)%n:-1;
}
2、求解线性同余方程
来源：https://www.cnblogs.com/lr599909928/p/12704583.html
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
using namespace std;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
int exgcd(int a,int b,int &x1,int &y1){
int x2,y2;
if(b==0){
x1=1,y1=0;
return a;
}
int d=exgcd(b,a%b,x2,y2);
x1=y2,y1=x2-a/b*y2;
return d;
}
int main() {
ios::sync_with_stdio(false);
int n;
cin>>n;
while(n--){
int a,b,m;
int x1,y1;
cin>>a>>b>>m;
int d=exgcd(a,m,x1,y1);
if(b%d) printf('impossible\n');
else printf('%lld\n',(ll)x1*(b/d)%m);
}
return 0;
}
3、求解不定方程
对于不定整数方程pa+qb=c，若 c mod Gcd(p, q)=0,则该方程存在整数解，否则不存在整数解。
上面已经列出找一个整数解的方法，在找到p * a+q * b = Gcd(p, q)的一组解p0,q0后，p * a+q * b = Gcd(p, q)的其他整数解满足：
p = p0 + b/Gcd(p, q) * t
q = q0 - a/Gcd(p, q) * t(其中t为任意整数)
至于pa+qb=c的整数解，只需将p * a+q * b = Gcd(p, q)的每个解乘上 c/Gcd(p, q) 即可。
在找到p * a+q * b = Gcd(a, b)的一组解p0,q0后，应该是得到p * a+q * b = c的一组解p1 = p0*(c/Gcd(a,b)),q1 = q0*(c/Gcd(a,b))，
p * a+q * b = c的其他整数解满足：
p = p1 + b/Gcd(a, b) * t
q = q1 - a/Gcd(a, b) * t(其中t为任意整数)
p 、q就是p * a+q * b = c的所有整数解。
用扩展欧几里得算法解不定方程ax+by=c;
代码如下：
代码
bool linear_equation(int a,int b,int c,int &x,int &y)
{
int d=exgcd(a,b,x,y);
if(c%d)
return false;
int k=c/d;
x*=k; y*=k; //求得的只是其中一组解
return true;
}
本文内容部分由信息学竞赛综合整理络，如有问题欢迎指正。