[数据结构与算法]扩展欧几里得算法及其简单应用

1. 整除与取模

先普及一下整除符号“|”
对于整数a,b(a≠0),若存在整数k,使b=ka,则称a整除b,或b能被a整除,记为a∣b。

然后是取模运算

取模运算不用说，大家都懂，不过有几条性质希望大家也都明白。

（a+b)%m = (a%m + b%m ) %m;

（a-b)%m = (a%m - b%m ) %m;

（a*b)%m = (a%m * b%m ) %m;

除法在这里是不成立的：（a/b)%m = (a%m / b%m ) %m; 这是错误的

2. 欧几里得算法

$$gcd(a,b)=gcd(b,a\%b)$$

若a<b,则gcd(a,b)=gcd(b,a)=gcd(b,a% b),命题成立。

若a>=b,不妨设a=q*b+r,其中0≤r<b。显然r=a%b。
对于a,b的任意公约数d, 因为d|a, d|(qb),故d|(a-qb), 即d| r, 因此d也是b,r的公约数。
对于b,r的任意公约数k, 因为k|b, k|(a-qb)\ [r=a-qb], 故k|a，因此k也是a,b的公约数
故a,b的公约数集合与b,a%b的公约数集合相同。于是它们的最大公约数自然也相等。

如果觉得不自然，请再往下看。

假设(a,b)>(b,a%b),令d等于a,b的最大公约数，即d=(a,b))
根据上面的推导可知:d同时也是b,r的公约数,而b,r的最大公约数一定大于等于d，假设不成立
假设(a,b)<(b,a%b)，和上面一样的道理，假设不成立。
(a,b)既不大于也不小于(b,a%b)，两者相等。

3. 最大公约数、最小公倍数

int gcd(int a,int b)
{
	if(b==0) return a;
    return gcd(b,a%b);
}

int lcm(int a,int b)
{
    return a/gcd(a,b)*b;
}

4. 扩展欧几里得算法

满足ax+by=(a,b) 时，可以用扩展欧几里得算法求出一组特解 ( x0 , y0 )

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

$$\begin{gathered} ax+by=bx+(a\%b)y=ay+(x?a/b?y)b \\ 于是我们可以不断递归至b=0，使得 \\ ax+by=(a,0)=a,x=1,y=0; \end{gathered}$$

5. ax+by=n

5.1 有解条件

$$当且仅当n是gcd(a,b)的倍数时，才有整数解。$$

5.2 求解步骤

$$\begin{gathered} 1.判断ax+by=n是否有整数解，有解的条件是gcd(a,b)|n \\ 2.求ax+by=d=(a,b)的一个解(x_0,y_0) \\ 3.在得到的a{x}_0+b{y}_0=d两边同时乘n/d得到a{x}_0?n/d+b{y}_0?n/d=n \\ 4.对照ax+by=n得到它的一个解x=x_0?n/d,y=y_0?n/d \\ 5.它的通解表达式为x=x+b/dy=y?a/d \end{gathered}$$

如果要求x的最小正整数解，令t=b/d x=(x%t+t)%t; 求y同理

5.3 代码

int slove(int a,int b,int n)
{
	int x,y;
	int d=exgcd(a,b,x,y);
	if(n%d) return -1;
	x=x*n/d;
	int t=b/d;
	if(t<0) t=-t;
	return (x%t+t)%t;
}

6. 同余方程

1.同余

两个整数a、b和正整数m ，如果a除以m所得的余数和b除以m所得的余数相等，即a %m=b%m.

称a和b对于m同余.m称为同余的模。同余的概念也可以这样理解: m l(a-b)。即a-b是m的整数倍。

例如 6|(16-4）16和4对6同余。同余的符号记为
$$a\equiv b(modm)$$

2.同余方程

$$ax\equiv b(modm)$$

$$\begin{gathered} ax?b是m的整数倍，即满足ax?b=my其中y可以是负数 \\ 于是可以改写为ax+my=b \end{gathered}$$
于是解同余方程就变成了求解二元一次不定方程，用扩展欧几里得算法，有解条件是gcd(a,m)能整除b

7. 逆元

什么是逆元？百度百科：逆元

这里只讨论我们需要的乘法逆元：
$$满足ax\equiv 1(modm)的x，称为a在模m下的逆元，即ax模m等于1$$

int slove(int a,int m)
{
	int x,y;
	exgcd(a,m,x,y);
	return (x%m+m)%m;
}

除法取模

逆元有什么用？

求(a/b)%m，当a,b是很大的数时，作除法会损失精度

使用逆元可以避免除法：设k是b的逆元，则bk模m等于1
$$(\frac{a}{b}\%m)=(\frac{a}{b}\%m)?bk\%m=ak\%mod$$
于是a/b就变成了ak，是不是很nice