欧几里得算法

一、欧几里得（Euclid）算法

又称辗转相除法，用于求两数最大公约数。

$$(a,b)=(b,a\%b)$$

代码：

int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}

二、扩展欧几里得（Euclid）算法

用于求解方程 $$ax+by=(a,b)$$ 的所有整数解 $(x,y)$ 。

考虑 $$(a,b)=(b,a\%b)$$
$\because ax_1+by_1=(a,b),bx_2+(a\%b)y_2=(b,a\%b)$
$\therefore ax_1+by_1=bx_2+(a\%b)y_2$
$\because a\%b=a-a/b \times b$（其中 $/$ 为整除），整理一下，得：
$$ax_1+by_1=ay_2+b(x_2-(a/b)y_2)$$
于是得出 $x_1=y_2,y_1=x_2-(a/b)y_2$
如此往下，按照欧几里得算法的过程， $b$ 将变成 $0$ ，此时方程为
$$ax=(a,b)$$
而原来的 $(a,b)$ 即为现在的 $a$ ，于是得到方程的一组特解 $x=1,y=0$ ，再逐层向上返回，便可以得到原方程的一组特解 $(x_0,y_0)$ 。
对于该方程的通解，可以由已经求出的特解推出。
在 $$ax+by=(a,b)$$ 中，使 $x$ 仍为整数且满足方程的最小变化量应为 $\frac{b}{(a,b)}$ ，同时 $y$ 改变 $\frac{a}{(a,b)}$ ，可以代入原方程检验，方程仍成立。
对于更一般的情况 $$ax+by=c$$
若 $(a,b) \nmid c$ ，则无解；
若 $(a,b) \mid c$ 且 $c=k \cdot (a,b)$ ，其所有整数解即为方程 $ax+by=(a,b)$ 的所有整数解解 $(x,y)$ 的 $k$ 倍，即 $(kx,ky)$ 。

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