歐幾裡得算法
歐幾裡得算法有一個為更多人所知的名字叫“輾轉相除法”，它是用來求解兩個數的最大公約數的算法
其計算原理依賴于下面的定理：
定理：
兩個整數的最大公約數等于其中較小的那個數和兩數相除餘數的最大公約數。最大公約數（greatest common divisor）縮寫為gcd。
即：gcd(a,b) = gcd(b,a mod b) (不妨設a>b 且r=a mod b ,r不為0)
通過這個定理，我們可以很快的求解出兩個數的最大公約數
下面我們來看代碼
int GCD(int a,int b){
return b?GCD(b,a%b):a;
}
用遞歸的方式寫出來，非常的清晰，也很好記，能如此簡潔也正是因為利用了之前所說的定理
擴充歐幾裡得算法
擴充歐幾裡得算法的思想基于以下定理：
對于不完全為 0 的非負整數 a，b，gcd（a，b）表示 a，b 的最大公約數，必然存在整數對 x，y ，使得 gcd（a，b）=ax+by。
關于這個定理，我們可以看一下一下這個例子（引用自數論概論，機械工業出版社）
這個例子中，左邊是歐幾裡得算法(gcd(60,22))，右邊是擴充歐幾裡得算法（60x+22y=gcd(60,22)）
可以看出，通過歐幾裡得算法的中間商和餘數可以解出方程gcd(a,b)=ax+by，那麼，為什麼可以這樣呢？我們來看一個通解的形式
一行行進行，我們可以找到規律：最新餘數=a的倍數+b的倍數
我們最後得到的非零餘數，他等于gcd(a,b)，這就給出了方程gcd(a,b)=ax+by的一組特解
這便是擴充歐幾裡得算法的思想，下面我們來看代碼
int Ex_GCD(int a,int b,int &x,int &y){
if(b==){
x=;
y=;
return a;
}
int ans=Ex_GCD(b,a%b,x,y);
int tmp=x;
x=y;
y=tmp-a/b*y;
return ans;
}
通過這樣的代碼，我們就可以很友善的解出方程gcd(a,b)=ax+by的一組特解(x0,y0)，它的通解我們可以用以下式子求出：
x = x0 + (b/gcd)*t
y = y0 – (a/gcd)*t
那麼，擴充歐幾裡得算法能幹些什麼呢？它一般有以下幾種用途：
1.求解ax+by=c的整數解
2.求模線性方程求模線性方程ax≡b(mod n)的最小解
3.求乘法逆元
4.求解模方程a^x≡b(mod n)
下面我們來一一介紹
1、求解ax+by=c的整數解
ax+by=gcd(a,b)=g的一組解為(x0,y0),則ax+by=c的一組解為(x0*c/g,y0*c/g)。當c不是g的倍數時無整數解。若(x1,y1)是ax+by=c的一組解，則其任意整數解為(x1+k*bb,y1-k*aa)，其中aa=a/gcd(a,b) ，bb=b/gcd(bb)，k為任意整數
2、求模線性方程求模線性方程ax≡b(mod n)的最小解
這個直接看代碼吧非常好了解
int modequ(int a,int b,int n){
int x,y,d,b1;
d=Ex_GCD(a,n,x,y);
if(b%d) return -;
b1=(n/d)<?-n/d:n/d;
x*=b/d;
return (x%b1+b1)%b1;
}
3、求乘法逆元
逆元：a*x≡1（mod m），其中，x為a關于m的逆元
一開始看到這句話大家可能會比較懵，就我的經驗來了解，逆元的用途就是：如果一個數a要除以一個很大的數b，兩個數都模m，那麼，這個運算等價于a乘以b關于m的逆元
下面來看代碼
int inv(int a,int m){
int x,y;
int gcd=Ex_GCD(a,m,x,y);
if(%gcd!=) return -;
x*=/gcd;
m=abs(m);
int ans=x%m;
if(ans<=) ans+=m;
return ans;
}
4、求解模方程a^x≡b(mod n)
這個也不多說，直接上代碼
//n為素數，無解傳回-1
int log_mod (int a,int b,int n){
int m,v,e=,i;
m=ceil(sqrt(n+));
v=inv(pow_mod(a,m),n);
map<int,int>x;
x[]=;
for(i=;i<m;i++){
e=(e*a)%n;
if(!x.count(e))x[e]=i;
}
for(i=;i<m;i++){
if(x.count(b))return i*m+x[b];
b=(b*v)%n;
}
return -;
}
到此，歐幾裡得算法與擴充歐幾裡得算法的介紹就結束了，題目推薦大家可以去百度一下，有很多題目分類文章，我在此就不列舉了