扩展欧几里得

问题描述

对于三个整数 a, b , c. 求解 \(ax+by=c\) 的( x , y )的整数解。

算法解决

首先我们要判断是否存在解，对于这个这个存在整数解的充分条件是 c 是 gcd(x,y) 的倍数。

朴素欧几里得

对于求解 gcd(x,y) 我们需要用 朴素欧几里得定理 。

gcd(a,b)=gcd(b,a%b).

这个比较好证明。

假设\(a=k\times b+r\) ,有r=a mod b，不妨设 d 为 a 和 b 的一个任意一个公约数，则有a ≡ b ≡ 0 ( mod d).

由于同余的性质 \(a-k\times b\)≡ r ≡ 0 (mod d)。因此 d 是 b 和 a mod b 的公约数。

然后任意一个公约数都满足，所以这个定理成立。

代码：

int gcd(int x,int y)
{
    if(y==0)
        return x;
    else
        return gcd(y,x%y);
}

这个复杂度是 O(log) 的，十分迅速。

然后判定是否有解后，我们需要在这个基础上求一组解 (x,y)，由于 a,b,c 都是 gcd (a,b) 的倍数。

对于 a,b 有负数的情况，我们需要将他们其中一个负数加上另外一个数直到非负。（由于前面朴素欧几里得定理是不会影响的）两个负数，直接将整个式子反号，然后放到 c上就行了。

我们将它们都除以 gcd (a,b)，不影响后面的计算。

也就是我们先求对于 ax+by=1且 （a和 b互质）求 (x,y) 的解。

接下来我们利用前面的朴素欧几里得定律推一波式子。

**\(ax+by=gcd(a,b)\) **

		$=gcd(b,a mod b)$

可得 bx+(a mod b)y=bx+(a-[\(\frac{a}{b}\)]b)y

								= ay+b(x-[$\frac{a}{b}$]y)

不难发现此时 x 变成了 y ， y 变成了 x??a/b? y，利用这个性质，我们可以递归的去求解 (x,y) 。

边界条件其实和前面朴素欧几里得是一样的b=0 的时候，我们有 a=1,ax+by=1 那么此时x=1,y=0 。

这样做完的话我们用 O(log) 的时间就会得到一组 (x,y) 的特殊解。

解系扩展

**注意：这里的x和y是 \(ax+by=gcd(a,b)\) 的一组特殊解 **

(d是整数)

\(x=x_0+db\)

\(y=y_0-da\)

代码：

代码说明，现根据普通欧几里得算法逐步深入到最底层（b=0），在一步一步回归

int exgcd(int a, int b, int& x, int& y)
{
	if (b == 0)
    {
		x = 1, 
        y = 0;
		return a;
	}
	int q = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return q;
}

要想求\(ax+by=c\)的解：

只要将\(ax+by=gcd(a,b)\) 的一组特解\(x_0\),\(y_0\)做如下变化：

\(x=x_0 \times c \div gcd(a,b)\)

\(y=y_0 \times c \div gcd(a,b)\)

x,y即为一组特解。

解析扩展

（d是整数）\(b_1=b \div gcd(a,b)\) , \(a_1=a \div gcd(a,b)\)

\(x=x_0+db_1\)

\(y=y_0-da_1\)

扩展欧几里得算法求解得到的一组特解\(x_0\)\(y_0\)是\(ax+by=gcd(a,b)\)的一组解

扩展欧几里德算法的应用主要有以下两个方面：

• 求解不定方程；

• 求解模线性方程（线性同余方程）与逆元；

（1）求解不定方程；

1.对于不定整数方程ax+by=m，若 m mod gcd (a, b)=0,则该方程存在整数解，否则不存在整数解。

先求\(ax+by=gcd(a,b)\),将得到的特解\(x_0\)\(y_0\)乘上c除以gcd(a,b),即

\(x_1=x_0 \times m \div gcd(a,b)\)

\(y_1=y_0 \times m \div gcd(a,b)\)

而，\(x_1\)\(y_1\)是方程ax+by=m的一组特解。

方程ax+by=m，的通解是：

（d是整数）\(b_1=b \div gcd(a,b)\) , \(a_1=a \div gcd(a,b)\)

\(x=x_0+db_1\)

\(y=y_0-da_1\)

（2），求解同余方程

求关于x的同余方程\(ax\) ≡ 1 (mod b) 的最小正整数解。

上式可以转化成\(ax+by=1\)，

若存在正整数解，则1 mod gcd(a,b) = 0,也就是说，a 和 b 互质时，有解。

代码：

long long x, y;//目前方程真正的解
//下面的函数执行完，得到一组方程的解（x，y）
long long exgcd(long long a, long long b, long long& x, long long& y)
{
	if (b == 0)
    {
		x = 1, 
        y = 0;
		return a;
	}
	long long q = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return q;
}

为了得到最小正整数解，需要解系扩展。

(d是整数)

\(x=x_0+db\)

\(y=y_0-da\)

x>0时，x需要减小许多b从而达到最小正整数解，即x=x%b;
x<0时，x需要加上许多b从而达到最小正整数解,即x=x%b+b
综合起来：
x = (x % b + b) % b;