正式敘述前還寫了一點自己的小感受。

問題：求兩個正整數a，b的最大公約數。

大神看來是很簡單的問題，但是對于去年夏天剛學python的我來說，這是個很難的問題，還記得當時一晚上睡不著都在想怎么快一點的求出最大公約數，后來猜測最小公倍數的求法，還有最后想出來的欣喜若狂，我現在還記憶猶新。

?

還記得看過一個小梗：一個農民種著種著地，一排一排的種，突然陷入深思，沉思良久，回去算了很久以后，借了錢瘋了似的坐火車跑到中科院門口，等來數學系教授，向他講述了自己的重大發現。大概意思就是，自己從田地中大徹大悟，發明了一種快速計算方法，不用計數，不用加法，不用數學，還給了教授一張偉大的定律表。

教授告訴他：你真的很厲害，你的發現很偉大，能在種田中悟出來這種算法可不容易。

?

?

?

?

?

?

?

但是，你發明的這種算法叫乘法，你給我的表，完善一下以后，叫九九乘法表。

農民繼續回去種田

（這個故事告訴我們要多虛心接受知識，不要老自己想。。。。）

?

我知道了歐幾里得算法以后，感覺自己就跟這個農民一樣。。。。。。。

不過，知道了自己的想法就是歐幾里得算法時，還是挺高興的。。。

就當鍛煉思維了吧。。只能這么安慰自己。

?

好，開始正題。。。。：：

?

我當時的思路是這樣的：求a，b的最大公約數，假設最大公約數是x的話，a一定可以用i*x來表示，b也一定可以用j*x來表示，我們怎么把i和j去掉，把x榨出來呢？？

讓這倆數不斷互相相減就可以啦！

后來自己想到了互相取余。

?

我們來看正規的歐幾里得算法：

首先放簡介：歐幾里德算法又稱輾轉相除法，是指用于計算兩個正整數a，b的最大公約數。應用領域有數學和計算機兩個方面。計算公式gcd(a,b) = gcd(b,a mod b)。

看代碼實現：

Python

def gcd(a, b):while a != 0:a, b = b % a, areturn b

?

后來知道了歐幾里得還有拓展：

可以用來求二元一次方程的通解，還可以用來求乘法逆元。?

已知整數a、b，擴展歐幾里得算法可以在求得a、b的最大公約數的同時，能找到整數x、y（其中一個很可能是負數），使它們滿足貝祖等式ax+by=gcd(a,b)

如果a是負數，可以把問題轉化成|a|(-x)+by=gcd(|a|,b)?，然后令x'=(-x)。

//返回 d=gcd(a,b); 和對應于等式 ax+by=d 中的 x,y
long long extend_gcd(long long a,long long b,long long &x,long long &y)
{if(a==0&&b==0) return ?1;//無最大公約數if(b==0){x=1;y=0;return a;}long long d=extend_gcd(b,a%b,y,x);y?=a/b*x;return d;
} 

求逆元，真的不想敘述了，上個代碼算了

 //********* 求逆元 *******************
//ax = 1(mod n)
long long mod_reverse(long long a,long long n)
{long long x,y;long long d=extend_gcd(a,n,x,y);if(d==1) return (x%n+n)%n;else return ?1;
} 

逆元，利用歐拉：

mod 為素數, 而且 a 和 m 互質?

long long inv(long long a,long long mod)//為素數mod
{return pow_m(a,mod?2,mod);
}

?

?