数论-(扩展)欧几里得算法辨析

欧几里得算法

欧几里得算法链接:传送门
欧几里得算法就是

我们通常说的“辗转相除法”

1
2
3
4
inline int gcd(int a,int b)
{
return b==0 ? gcd(y,x%y);
}

扩展欧几里得

扩展欧几里得是用来求:已知$(a,b)$时,求解一组$(p,q)$,使得$p\times a+q\times b=gcd(a,b)$。
(根据裴蜀等式,一定存在整数解:裴蜀等式的介绍在靠后的位置
这里要纠正一下:扩欧不一定是用来求逆元的!!!当$a$和$b$互质的时候才是用来求逆元。
证明$by$《数学一本通》

∵$gcd(a,b)=gcd(b,a\mod b)$
∴$p\times a+q\times b=gcd(a,b)=gcd(b,a\mod b)=p\times b+q\times a\mod b =q\times b+q\times(a-a/b\times b)=q\times a+(p-a/b\times q)\times b$;
所以我们就把$a,b$的线性组合化简为$b,a\mod b$的线性组合。
根据前面的结论,$a$和$b$都在减小,如果$b$减小到0时候,就可以得出$p=1,q=0$。然后递归回去就可以求出最终的$p、q$了。

这里我们给出来自一位大佬的解释:
传送门

现在我们知道了 a 和 b 的最大公约数是 gcd ,那么,我们一定能够找到这样的 x 和 y ,使得: ax + by = gcd 这是一个不定方程(其实是一种丢番图方程),有多解是一定的,但是只要我们找到一组特殊的解 x0 和 y0 那么,我们就可以用 x0 和 y0 表示出整个不定方程的通解:
x = x0 + (b/gcd)t
y = y0 – (a/gcd)
t
为什么不是:
x = x0 + bt
y = y0 – a
t
这个问题也是在今天早上想通的,想通之后忍不住喷了自己一句弱逼。那是因为:
b/gcd 是 b 的因子, a/gcd 是 a 的因子是吧?那么,由于 t的取值范围是整数,你说 (b/gcd)t 取到的值多还是 bt 取到的值多?同理,(a/gcd)t 取到的值多还是 agcd 取到的值多?那肯定又要问了,那为什么不是更小的数,非得是 b/gcd 和a/gcd ?
注意到:我们令 B = b/gcd , A = a、gcd , 那么,A 和 B 一定是互素的吧?这不就证明了 最小的系数就是 A 和 B 了吗?要是实在还有什么不明白的,看看《基础数论》(哈尔滨工业大学出版社),这本书把关于不定方程的通解讲的很清楚
现在,我们知道了一定存在 x 和 y 使得 : ax + by = gcd , 那么,怎么求出这个特解 x 和 y 呢?只需要在欧几里德算法的基础上加点改动就行了。
我们观察到:欧几里德算法停止的状态是: a= gcd , b = 0 ,那么,这是否能给我们求解 x y 提供一种思路呢?因为,这时候,只要 a = gcd 的系数是 1 ,那么只要 b 的系数是 0 或者其他值(无所谓是多少,反正任何数乘以 0 都等于 0 但是a 的系数一定要是 1),这时,我们就会有: a1 + b0 = gcd
当然这是最终状态,但是我们是否可以从最终状态反推到最初的状态呢?
假设当前我们要处理的是求出 a 和 b的最大公约数,并求出 x 和 y 使得 ax + by= gcd ,而我们已经求出了下一个状态:b 和 a%b 的最大公约数,并且求出了一组x1 和y1 使得: bx1 + (a%b)y1 = gcd , 那么这两个相邻的状态之间是否存在一种关系呢?
我们知道: a%b = a - (a/b)b(这里的 “/” 指的是整除,例如 5/2=2 , 1/3=0),那么,我们可以进一步得到:
gcd = b
x1 + (a-(a/b)b)y1
= bx1 + ay1 – (a/b)by1
= ay1 + b(x1 – a/by1)
对比之前我们的状态:求一组 x 和 y 使得:a
x + by = gcd ,是否发现了什么?
这里:
x = y1
y = x1 – a/b
y1

给出代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int extended_gcd(int a,int b,int &x,int &y)
{
int ret,tmp;
if(!b)
{
x=1;
y=0;
return a;
}
ret=extended_gcd(b,a%b,x,y);
tmp=x;
x=y;
y=tmp-a/b*y;
return ret;
}

扩展欧几里得求解线性方程

根据前面的“裴蜀等式”,我们知道方程$a\times x+b\times y=c$一定有解的充分必要条件是$gcd(a,b)|c$。于是乎,我们求这个方程的解的步骤就是求出$a\times x+b\times y=gcd(a,b)$的一组解,然后两边同除以$gcd(a,b)$,乘上$c$就可以了。

再特殊地,如果$a$和$b$互质,且$x_0y_0$是$a\times x+b\times y=c$的一组解,那么这方程的任意一个解都可以表示为$x=x_0+b\times t,y=y_0-a\times t$。$t$取任何整数都成立。
代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int extended_gcd(int a,int b,int &x,int &y)
{
int ret,tmp;
if(!b)
{
x=1;
y=0;
return a;
}
ret=extended_gcd(b,a%b,x,y);
tmp=x;
x=y;
y=tmp-a/b*y;
return ret;
}
bool linearEquation(int a,int b,int& x,int& y)
{
int d=Extended_gcd(a,b,x,y);
if(c%d)return false;
int k=c/d;
x*=k;
y*=k;
return true;
}

扩欧求逆元

逆元是什么?逆元在这里
若$a\times x\equiv 1\pmod b$,$a,b$互质,我们就说$x$是$a$的逆元,记为$a^{-1}$。
根据逆元的定义,我们可以转化为求这个方程$a\times x+b\times y=1$,用扩欧求解;
代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void exgcd(int a,int b,int c,int &x,int &y)
{
int ret,tmp;
if(a==0)
{
x=0;
y=c/b;
return;
}
int tx,ty;
exgcd(b%a,a,c,tx,ty);
x=ty-(b/a)*tx;
y=tx;
return;
}

exgcd其他风格

结构体风格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
long long a,b;
struct Triple
{
long long d,x,y;
};
Triple exgcd(long long a,long long b)
{
if(b==0)
{
return (Triple){a,1,0};
}
Triple t=exgcd(b,a%b);
return (Triple){t.d,t.y,t.x-a/b*t.y};
}

单函数exgcd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int x,y;
void exgcd(int a,int b,int c,int &x,int &y)
{
if(a==0)
{
x=0;
y=c/b;
return;
}
else
{
int tx,ty;
exgcd(b%a,a,c,tx,ty);
x=ty-(b/a)*tx;
y=tx;
return;
}
}
文章目录
  1. 1. 欧几里得算法
  2. 2. 扩展欧几里得
  3. 3. 扩展欧几里得求解线性方程
  4. 4. 扩欧求逆元
  5. 5. exgcd其他风格
    1. 5.1. 结构体风格
    2. 5.2. 单函数exgcd