抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

tuozhanoujilide

欧几里得算法

欧几里得算法又称辗转相除法,用于求两个数的最大公因数,代码如下:

1
2
3
int gcd(int a, int b){
return b == 0 ? a : gcd(b,a%b);
}

例如:当a = 75, b = 48 时,过程如下,

gcd

拓展欧几里得

这种算法,它可以在辗转相除途中求出不定方程 $ax+by=c$的一组解。

在上图中,倒数第二行的等式$3+6\ast3=21$可以移项写为$3=6\ast(-3)+21$,此时3可以表示为6和21的线性组合。

倒数第三行6的线性组合$6=21\ast(-1)+27$,则3又可以被表示为$3=(21\ast(-1)+27)\ast(-3)+21=27\ast(-3)+21\ast4$

以此类推,则3可以表示为75和48的线性组合,就可以找到$75x+48y=3$的解了。

3是75和48的最大公因数,经过上面的步骤可得求$ax+by=c(c == gcd(a,b))$的解,如果c是其他的数还可以用这个方法吗,实际上,c必须是gcd(a,b)的倍数,如下:

$ax+by=c$两边同时除以gcd(a,b)得$\frac{ax}{gcd(a,b)}+\frac{by}{gcd(a,b)}=\frac {c}{gcd(a,b)}$,方程左边都为整数,则c为gcd(a,b)的倍数才能使得方程成立。

算法代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int exgcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}

int d = exgcd(b, a % b, x, y);
int x0 = x;
int y0 = y;
x = y0;
y = x0 - (a / b) * y0;
return d;
}

简洁写法如下:

1
2
3
4
5
6
7
8
9
10
int exgcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}

int d = exgcd(b, a % b, y, x); //这里交换了x,y;
y -= (a / b) * x;
}

这样就得到了一组特解,如何求通解呢?

设除了特解之外还有一组解$x_1=x+t、y_1$,那么由$ax_1-at+by=gcd(a,b)$得$ax_1+b(y-\frac{a}{b}t)=gcd(a,b)$,可得,$y_1=y-\frac{a}{b}t$。

这里必须保证$t$和$\frac{a}{b}t$都是整数,设后者等于$\frac{a’}{b’}t$,$a’=\frac{a}{gcd(a,b)},b’=\frac{b}{gcd(a,b)}$。由于$a’$与$b’$互质,$t$应当为$kb’(k\in Z)$,

即:

$$
{\begin{matrix}
x_k = x+k\frac{b}{gcd(a,b)}\
y_k = y-k\frac{a}{gcd(a,b)}\
(k\in Z)\
\end{matrix}
$$

这便是该不定方程的通解

例题

题目描述
求关于$x$的同余方程 $ax \equiv 1 \pmod {b}$的最小正整数解。

输入格式
一行,包含两个正整数 $a,b$用一个空格隔开。

输出格式
一个正整数 $x_0$ ,即最小正整数解。输入数据保证一定有解。

$ax \equiv 1 \pmod {b}$等价于$ax-1=yb$,即$ax-by=1$,由于$y$可以是负数,改写为$ax+by=1$,至此,可以使用拓展欧几里得进行求解。由于有解条件为$gcd(a,b)=1$,即a,b互质,则通解$x_k=x+kb$。题目需求x的最小正整数解,对$x+b$取$b$的模即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

int exgcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int d = exgcd(b, a % b, x, y);
int x0 = x, y0 = y;
x = y0;
y = x0 - (a / b) * y0;
return d;
}
int main() {
int a, b;
int x, y;
cin >> a >> b;
exgcd(a, b, x, y);
cout << (x + b) % b << endl;
return 0;
}

评论