拓展欧几里得

拓欧

欧几里德算法（辗转相除法）

内容

$\forall a,b \in \mathbb{N},b \ne 0,$ 有 $gcd(a,b)=gcd(b,a \bmod b)$

证明：

• 若 $a<b$ ，则 $gcd(b,a \bmod b)=gcd(b,a)=gcd(a,b)$
• 若 $a \ge b$ 设 $a=q \times b +r$ ,其中 $0 \le r <b$ ,则 $gcd(b,a \bmod b)=gcd(b,r)$ 。对于 $a,b$ 的任何公约数 $d$ ，必有 $d|a,d|b$ ，故 $d|q \times b$ ，故 $d|(a-(q \times b))$ ，即 $d|r$ 。因此， $d$ 也是 $r,b$　的公约数，于是 $gcd(a,b)=gcd(r,b)$

代码

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

时间复杂度为 $O(\log{(a+b)})$

裴蜀定理

内容

$\forall a,b,c \in \mathbb{Z}$ 关于 $x,y$ 的不定方程 $ax+by=c$ 有整数解当且仅当 $gcd(a,b)|c$ ，且一定存在 $x,y$ 使 $c=gcd(a,b)$

该定理的正确性初中就学过了，这里再简要证明一下：

设 $d=gcd(a,b)$ ，则 $d|a,d|b$ ，故 $d|(ax+by)$ 。
再设 $s$ 为 $ax+by$ 当 $x,y\in \mathbb{Z}$ 时能取得的最小正值。设 $r=a \bmod s=a-\left \lfloor \frac{a}{s} \right \rfloor \times s=a-\left \lfloor \frac{a}{(ax+by)} \right \rfloor \times (ax+by) =a(1-\left \lfloor \frac{a}{ax+by} \right \rfloor x)+b(-\left \lfloor \frac{a}{ax+by} \right \rfloor y)$ ，这里的 $x,y$ 是常量，使 $ax+by=s$ 。
可见 $r$ 是 $a,b$ 的线性组合，由于 $r= a \bmod s$ ，故 $0 \le r< s$ 。
而 $s=ax+by$ 是 $a,b$ 线性组合的最小正值，故 $r=0$ 。因此 $s|a$ 。
同理， $s|b$ 。
故 $s$ 是 $a,b$　的公约数，故 $s|d$ 。
又因为 $d|(ax+by)$ ，故有 $d|s$ ，那么只能 $d=s$ ，命题得证。

特解

有了裴蜀定理，我们就可以解出 $ax+by=gcd(a,b)$ ，代码如下：

int exgcd(int a,int b,int& x,int& y){
	if(!b){
   		x=1,y=0;
      return a;
   }
   int d=exgcd(b,a%b,y,x);//这里交换了x和y
   y-=(a/b)*x;
   return d;
}

当我们调用函数 $d=exgcd(a,b,x_0,y_0)$ 时，由于 $x,y$ 是实参，结束后 $x_0,y_0$ 即为一组特解， $d$ 为 $gcd(a,b)$ 。

那么，由于 $d|c$ , $ax+by=c$ 的通解为：

$$
\begin{align}
x=\frac{c}{d}x_0+k\frac{b}{d} \\
y=\frac{c}{d}y_0-k\frac{a}{d}
\end{align}
$$

其中 $k$ 取遍 $\mathbb{Z}$ ，$d=gcd(a,b)$ ，$x_0,y_0$ 是方程 $ax+by=gcd(a,b)$ 的一组特解

练习

P1082
我们发现 $ax \equiv 1 \pmod{b}$ ，就等价于 $ax=by+1$ 移项得 $ax-by=1$ 。

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a,m; 
LL exgcd(LL a,LL b,LL& x,LL& y){		
	if(!b){	
		x=1,y=0;
		return a;
	}
	LL d=exgcd(b,a%b,y,x);		 
	y-=a/b*x;	
	return d;
}
int main(){
	scanf("%lld%lld",&a,&m);
	LL x,y;
	exgcd(a,m,x,y);
	x=(x%m+m)%m; 
	printf("%lld",x);
	return 0;
}