欧几里得算法
一、欧几里得(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;
}