1.歐幾里德算法

作用：對于給定的a,b，求a,b的最大公約數(shù)gcd(a,b)

要求：無

證明：我們先想證明\(gcd(a,b)=gcd(b,a\%b)\)

我們先證明\(gcd(a,b)=gcd(a-xb)\)

這樣，當(dāng)\(x=1\)時(shí)，他就是輾轉(zhuǎn)相除法\(gcd(a,b)=gcd(b,a-b)\)

當(dāng)\(x=\frac{a}\)，且除法向下取整，則此時(shí)\(gcd(a,b)=gcd(b,a\%b)\)

所以只要證明出來\(gcd(a,b)=gcd(a-xb)\)對于任意的\(x\)成立，我們就可以證明歐幾里德算法成立

真正的證明

設(shè)\(gcd(a,b)=c,gcd(b,a-xb)=d\)

根據(jù)性質(zhì)，可以寫出

\(\because c|a,c|b\)

\(\therefore c|(a-xb)\)

\(\therefore c|gcd(b,a-xb)\Leftrightarrow c|d\)

\(\because d|b \therefore d|(xb)\)

又\(\because d|(a-xb) \ \therefore d|a\)

\(\therefore d|gcd(a,b)\Leftrightarrow d|c\)

\(\because d|c\ \&\ c|d\)

\(\therefore c==d\)

所以，我們可以證明歐幾里德算法成立

代碼：

inline int gcd( int x , int y ){
    return y == 0 ? x : gcd( y , x % y ) ;
}

2.擴(kuò)展歐幾里德

作用：解出來二元一次方程組ax+by=c

要求：c%gcd(a,b)=0

實(shí)質(zhì)上，擴(kuò)展歐幾里德解的是\(a*x+y*b=gcd(x,y)\)，解出來的\(x,y\)是絕對值最小的解，有可能是負(fù)數(shù)。

那么，對于任意已知\(a,b,c\)的

我們都可以通過擴(kuò)展歐幾里德來求解，我們可以考慮先給全部式子都乘上 \(\large\frac{gcd(a,b)}{c}\)

那么，式子就會變成

這樣我們發(fā)現(xiàn)其實(shí)對于a,b這個(gè)式子就是一個(gè)擴(kuò)展歐幾里德了，只不過我們解出來的\(x_0,y_0\)分別是\(x_0*\frac{gcd(a,b)}{c},y_0*\frac{gcd(a,b)}{c}\)，我們只需要把求出來的\(x,y\)都乘上\(\frac{c}{gcd(a,b)}\)就可以了

但是我們發(fā)現(xiàn)\(\frac{c}{gcd(a,b)}\)是整數(shù)當(dāng)且僅當(dāng)\(c \% gcd(a,b)==0\)，這也就是上文中要求的由來

但是，我們還可以發(fā)現(xiàn)，其實(shí)這個(gè)方程肯定有無限組解，我們只求出來了一組特殊解，怎么推廣到全部呢？

我們可以把\(a*x+b*y\)寫成

那么，我們求出來的\(x,y\)都可以變成\((x-k*b),(y+k*a)\)

所以現(xiàn)在我們只需要考慮\(k\)的取值范圍就行了

但是觀察了許久，發(fā)現(xiàn)并沒有什么范圍

于是我們想，如果能讓\(k\)取遍他的定義域的同時(shí)求出所有解，那么這個(gè)\(k\)一定是唯一的，且不能再小，再小就會得到不正確的解，再大就不能得到所有解

我們讓\(k\)最小不就行了？

我們發(fā)現(xiàn)，我們只需要滿足\(k*a\)和\(k*b\)都是整數(shù)，其他方面沒有對\(k\)有過多要求

所以\(k\)的最小值就得到了，我們得\(k=\frac {1}{gcd(a,b)}*t \ |t\in Z\)

易得t取遍z的時(shí)候，所有解集就得到了

所以

對于

還有一個(gè)事情，就是最小正數(shù)解，我們只需要把\(x\)搞成\(((x\%b)+b)\%b\)就可以了，其實(shí)也就是\(x<0\)的時(shí)候\(x+=\frac{gcd(a,b)}\)

說了這么多，忘記證明擴(kuò)展歐幾里德的原理了

為什么我們可以求出\(x,y\)?

根據(jù)歐幾里德算法，我們知道
我們還知道，當(dāng)\(b=0\)時(shí)，\(a=gcd\)，算法停止

所以我們可以得到\(a*1+b*0=gcd\)

得到一個(gè)狀態(tài)后，我們只需要得到如何轉(zhuǎn)移狀態(tài)即可

由于

又由于\(a\%b==a-(a/b)*b\),這里除法向下取整

我們展開模運(yùn)算和gcd，可以得到

代碼

inline int exgcd( int a , int b , int & x , int & y ){
  if( b == 0 ){
    x = 1 , y = 0 ;
    return a ;  
  } int ans = exgcd( b , a % b , x , y ) ;
  int t = x ; x = y ; y = t - y * ( a / b ) ; 
  return ans ;
}

學(xué)會這個(gè)東西，有什么用處呢？其實(shí)最大的用處是求乘法逆元

3.乘法逆元

用處：解決\(（a/b）\%c \not=((a\%c)/(b\%c)\)的問題

我們知道\(（a/b）\%c \not=((a\%c)/(b\%c)\)，所以，如果\(a/b\)很大的話，我們?nèi)绾斡?jì)算呢？

這里就要引入一個(gè)乘法逆元,我們可以找到一個(gè)數(shù)\(x\),使得\(（a/b）\%c =((a\%c)*(x\%c))\%c\)
這個(gè)\(x\)就是\(b\)關(guān)于\(c\)的乘法逆元
\(x\)的計(jì)算方法是\(x*b≡1(mod\ c)\),由于\(b,c\)已知，我們只需要用擴(kuò)展歐幾里德解\(x*b+t*c=1\)
得到一個(gè)\(x\)，把\(x\)變成最小正整數(shù)解就可以了
在這種計(jì)算方法下，要求\(gcd(b,c)\%1=0\),也就是\(gcd(b,c)=1\)

還有一個(gè)求法，費(fèi)馬小定理\(x=b^{c-2}\),當(dāng)\(p\)是質(zhì)數(shù)的時(shí)候成立，需要打一個(gè)快速冪。

這兩種復(fù)雜度都是\(log(n)\)，都用于求一個(gè)數(shù)的乘法逆元，擴(kuò)歐的要求更少。

如果一道題我們需要求\(1~n\)的乘法逆元，那么我們的復(fù)雜度是\(nlog(n)\)，但是其實(shí)還有一種更快的方法

證明不太會，以后再說，直接給代碼

int inv [N] ;
inv [1] = 1 ;
for( int i = 2 ; i <= n ; i ++ )//i mod p 的逆元 
  inv [i] = ( p - （ p / i ） ) + inv [p % i] % p ;