扩展欧几里得
从欧几里得讲起……
欧几里得的辗转相除法计算的是两个自然数a和b的最大公约数g,意思是能够同时整除a和b的自然数中最大的一个。
两个数的最大公约数通常写成GCD(a, b),或者简写成(a, b)。
(Greatest Common Divisor)
计算方法……辗转相除!
作为数论中一个很基础的内容,它的形式很漂亮,代码也很干净。
$$gcd(a,b) = gcd(b,a % b)$$
证明过程
令$r = a % b$则有$a = k \times b + r$故可知$r = a - k \times b$
现假设$d$是$a$,$b$的一个公约数
则有$d|a$ , $d|b$
又由上式可得$d|(a - k \times b)$即$d|r \iff d|(a%b)$
由此证明$d$也是$b$和$(a%b)$的公约数
即$gcd(a,b) = gcd(b,a%b)$
注:$d|a$表示$d$整除$a$
代码实现
long long gcd(long long a,long long b)
{ return b == 0 ? a : gcd(b,a%b); }
贝祖等式……问题的开端!
贝祖等式(又称裴蜀等式)是一个形如$ax + by = m$的方程。
而有整数解$(x,y) \iff m = k \times gcd(a,b) , k \in \mathbb Z$。
裴蜀等式有解时必然有无穷多个解。
补充:特别的,$ax + by = 1 \iff gcd(a,b)=1$
而利用辗转相除法可以得到这一方程的整数特解。
而且不难发现,大多数情况下$x$和$y$总是一正一负。
一段巧妙的证明
从$ax + by = gcd(a,b)$开始……
由于长得漂亮对称的结构,我们不妨设$a \gt b$
- 当$b = 0$时,$gcd(a,b) = a$这个时候我们的等式就变成了$ax = a$的形态不难看出这时候的一组解$(x,y) = (1,0)$
- 当$b \not= 0$时候,我们可以得到
$ax_1 + by_1 = gcd(a,b)$
$bx_2 + (a%b)y_2 = gcd(b,a%b)$
又由于$gcd(a,b) = gcd(b,a%b)$
所以有$ax_1 + by_1 = bx_2 + (a%b)y_2$
定义可得$a%b = a - \lfloor {\cfrac{a}{b}} \rfloor \times b$将其带入上式
$$ax_1 + by_1 = bx_2 + (a - \lfloor {\cfrac{a}{b}} \rfloor \times b)y_2$$
$$ax_1 + by_1 = bx_2 + ay_2 - (\lfloor {\cfrac{a}{b}} \rfloor \times b)y_2$$
由$a$和$b$的对应系数相等,所以可推出
$x_1 = y_2$
$y_1 = x_2 - \lfloor {\cfrac{a}{b}} \rfloor y_2$
综上,我们推导出了求该等式特解的边界条件和递推过程。
代码实现
注意 gcd , x , y 变量均使用引用传参,这是为了每一步都能改变原始数据。
void exgcd(long long a, long long b, long long &gcd, long long &x, long long &y)
{
if (b == 0)
{
gcd = a;
x = 1;
y = 0;
return;
}
exgcd(b, a % b, gcd, x, y);
long long xt = x, yt = y;
x = yt;
y = xt - a / b * yt;
return;
}
应用举例
求解同余方程的最小正整数解$ax \equiv 1 (\mod b)$,给出$a$和$b$。
分析
$ax \equiv 1 (\mod b) \iff ax + by = 1$
其中$y$是我们引入的一个整数而且十有八九应该是负数。
但是有一个问题,$ax + by = 1$又不是$ax + by = gcd(a,b)$
这是怎么牵扯上关系的呢?还不是你乱点鸳鸯谱
由最大公约数的定义,总有$a|gcd(a,b)$而且$b|gcd(a,b)$
如果有$x,y \in \mathbb Z$则必定$(ax + by)|gcd(a,b)$
即若有$ax + by = m$则$m|gcd(a,b)$
当$m=1$时,就有$1|gcd(a,b)$
故而$gcd(a,b)$就只能等于$1$了
但是我们求出的$x$十有八九是负数也有可能太大,怎么得到最小正整数解呢?
$ax + by = 1$
$ax + by + k \times ab - k \times ab= 1$
$a(x + kb) + b(y - ka)= 1$
故而我们使用$(x’ % b + b)%b$的方式计算最终结果
这里一开始我不太明白
后来想想,我们要求的是$x’$在加上$k$个$b$之后最小的整数结果
前提:$x’ \lt 0, b \gt 0$
由$x’%b$可以将其结果限制在$[-b,0]$
当$-b \lt x’%b \lt 0$时候加$b$便是最终结果了
当$x’%b = 0$时候加$b$再对$b$取模便是0不会出现错误
这里涉及到负数的取模运算,但这个计算的结果是百家争鸣的,我们先以C++中的结果为准
在C++中,有$-7 % 3 = -1$
以$a = 3, b = 10$为例解得$x = -3,y = 1$
计算得到$(-3 % 10 + 10) % 10 = 7$
代码实现
void exgcd(long long a, long long b, long long &gcd, long long &x, long long &y)
{
if (b == 0)
{
gcd = a;
x = 1;
y = 0;
return;
}
exgcd(b, a % b, gcd, x, y);
long long xt = x, yt = y;
x = yt;
y = xt - a / b * yt;
return;
}
int main()
{
long long a,b;
long long g,x,y;
cin >> a >> b;
exgcd(a,b,g,x,y);
x = (x % b + b)%b;
cout << x << endl;
return 0;
}