在學習資訊學數論部分知識點的過程中，有兩個比較重要的算法，那就是歐幾裡得算法與擴充歐幾裡得算法。
今天，我們就帶大家一起來了解一下這兩個算法，看起來相似的算法到底分别是解決了什麼問題呢？
歐幾裡得算法
在學習一種算法前，我認為我們首先應該知道，這種算法是要解決什麼問題的。
國小就已經學過了兩個數的最大公約數，而歐幾裡得算法就是為了求出兩個數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;//一行代碼就是爽
拓展歐幾裡得算法
用來在已知的a、b中求解一組x、y，使得ax+by=gcd(a,b)成立（根據數論相關定理，這組解一定存在）。
了解一下貝祖定理：若存在a、b是整數，則必存在整數x、y，滿足ax+by=gcd(a,b)。
換句話說，如果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;
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;
聲明：部分資料來源于網絡，侵删。