擴充歐幾裡得+逆元

【傳送門】參考了幾位大神的資料，本蒟蒻表示不勝感激

http://chhaj5236.blog.163.com/blog/static/112881081200942542255916/（真心膜拜）

http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html

http://blog.sina.com.cn/s/blog_7064e7850100yeu1.html

【擴歐的求法】經典的歐幾裡得算法早就爛熟于心，但是對于擴歐我原來一無所知。擴充歐幾裡德主要是用來與求解線性方程相關的問題。現在假設一個方程為a*x+b*y=m，如果這個線性方程有解，那麼一定有gcd(a,b) | m，即a，b的最大公約數能夠整除m(m%gcd(a,b)==0)。

{證明}很簡單，由于a%gcd(a,b)==b%gcd(a,b)==0，是以a*x+b*y肯定能夠整除gcd(a,b)。

那麼以下是關于此方程的解法：

令a1=a/gcd(a,b)，b1=b/gcd(a,b)，P=m/gcd(a,b)。如果我們能夠首先求出滿足a*x1+b*y1=gcd(a,b)（即原式兩邊除以P）這個方程的x1和y1，那麼x=x1*P,y=y1*P就可以求出來了。由歐幾裡德算法gcd(a,b)=gcd(b,a%b)，是以a*x1+b*y1=gcd(a,b)=gcd(b,a%b)=b*x2+(a%b)*y2，現在隻要做一些變形就可以得到擴充歐幾裡德算法中的用到的式子了。令k=a/b(商)，r=a%b(餘數)，那麼a=k*b+r。是以r=a-k*b，帶入上式，得到a*x1+b*y1=b*x2+(a-(a/b)*b)y2=a*y2+b*(x2-(a/b)*y2) => x1=y2，y1=x2-(a/b)*y2。有了這兩個式子我們就知道了在用歐幾裡德求最大公約數的時候，相應的參數x，y的變化。現在再回過頭來看一下擴充歐幾裡德算法的代碼就很好了解了，實際上擴充歐幾裡德就是在求a和b的最大公約數的同時，也将滿足方程a*x1+b*y1=gcd(a,b)的一組x1和y1的值求了出來。

【代碼】

int exGcd(int a,int  b,int &x,int &y)
{
    if(b==0){x=1;y=0;return a;}
    int g=exGcd(b,a%b,x,y);
    int temp=x;x=y;
    y=temp-(a/b)*y;
    return g;
}
           

最後再乘上P，你懂的。這就是一組解。

【逆元】設我們要求a/b%p的值，我們可以轉化為a*x%p。顯然，(1/b)%p=x%p,x*b%p=1。

前提：gcd(x,b)=1.這樣的話，x就存在。

如何求解a*x%n=1的方程呢？我們可以化成ax+ny=1，然後在上述gcd中帶出。

【疑問】為什麼網上的逆元模闆都是有3個x和y的。= =