朴素的欧几里得算法大家应该知道

\(gcd(a,b)\)表示a,b的最大公约数

朴素的欧几里得算法其实就是所谓的辗转相除法

辗转相除法
\(gcd(a,b)=gcd(b,a\) \(mod\) \(b)\)
证明如下：
\(设r=a\) \(mod\) \(b\) \(=a-\lfloor\frac{a}{b}\rfloor*b\),\(p=gcd(a,b)\);
则\[a=xp,b=yp\]
代入可得\[r=xp-\lfloor\frac{xp}{yp}\rfloor*yp\]
提公因式得\[r=p(x-\lfloor\frac{xp}{yp}\rfloor*y)\]
所以\[p|r\]
即\[a,b的最大公约数也是r的约数\]
设\(p`=gcd(b,r)\)
则\[b=x`p`,r=y`p`\]
\[a=r+\lfloor\frac{a}{b}\rfloor*b\]
代入得\[a=y`p`+\lfloor\frac{a}{b}\rfloor*x`p`\]
提公因式\[a=p`(y`+\lfloor\frac{a}{b}\rfloor*x`)\]
所以\[p`|a\]
得出结论：a,b与b,a mod b的公约数相同，所以最大公约数也相同
得证；

Code：

int gcd(int a,int b) {    if(!b) return a;     else return gcd(b,a%b);}

扩展欧几里得算法

扩展欧几里得算法就是在朴素的欧几里得算法上求一组未知数(x,y)的解，满足贝祖定理:\(ax+by=gcd(a,b)\)

公式的推导
当且仅当\(a>b\)
①\(b=0\) 则\(x=1,y=0\)
②\(a>b>0\)
设\(ax1+by1=gcd(a,b);bx2+(a\) \(mod\) \(b)y2=gcd(b,a\) \(mod\) \(b)\)
由朴素欧几里得算法得：\(gcd(a,b)=gcd(b,a\) \(mod\) \(b)\)
所以\(ax1+by1=bx2+(a\) \(mod\) \(b)y2\)
即\(ax1+by1=bx2+(a-\lfloor\frac{a}{b}\rfloor*b)y2\)
化简得：\(ax1+by1=bx2+ay2-\lfloor\frac{a}{b}\rfloor*b*y2\)
由贝祖等式得\(\left\{\begin{array}\\x1=y2\\{y1=x2-\lfloor\frac{a}{b}\rfloor*b} \end{array}\right.\)
##Code:

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 z=x;    x=y;y=z-a/b*y;    return r;}