欧几里德&扩展

主要内容：

1. 求余运算基础
2. 欧几里德算法(gcd)
3. 二元一次方程
4. 扩展欧几里德算法（exgcd）

1、求余运算基础

在c++语言中，求余运算符号为%，如 10 % 3 = 1，对应地整除运算为/，如10/3 = 3。

对于整数n和m，将他们表示i为 n = m*x + r，0<=r<m，则x称为商，r称为余。

以上公式也可以表示为： x = n/m，r=n%m。

2、欧几里得算法

欧几里得算法也称辗转相除法，用来快速计算两个正整数的最大公约数。

定义gcd(a, b)为a和b的最大公约数（假设a>b），则有

引理：gcd(a, b) = gcd(b, a%b) = .... = gcd(r, 0) = r

根据引理，就可以使用递推（递归）来求最大公约数。

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

3、二元一次方程

形如ax + by = c的方程，称为二元一次方程（两个变量x和y，次数都为1）。

条件：

• 贝祖定理：有解的充分必要条件：c是gcd(a, b)的倍数。
• 特殊情况：gcd(a, b)=1时，ax + by = 1有解

求解：以ax + by = 1为例，可以用枚举的方法求解：从0到b-1枚举，找到ax-1能被b整除的数。

转换：如果是a*x + by = c，gcd(a, b) | c （这里| 表示整除），令gcd(a, b) = m，可转换方程为：

a' * x + b' * y = c'， a' = a/m, b'=b/m, c'=c/m

先求解 a' * x + b' * y = 1 ，然后将解 乘上 c'即可。

多组解：

• 二元一次方程有很多组解，假设(x0, y0)是解，则(x0+b, y-a)和(x0-b, y+a)也都是解。

  a*(x0+b) + b*(y0-a) = a*x0 + b*y0 = c
  a*(x0-b) + b*(y0+a) = a*x0 + b*y0 = c
  

• 对于ax+by=c，gcd(a, b)=1，则在[1..b]之间有唯一解（最小正整数解）
• 对于ax+by=d, gcd(a, b)=r, r|d，则在[1..b/d]之间有唯一解（最小正整数解）

4、扩展欧几里得算法

扩展欧几里得算法使用辗转相除法来快速求解二元一次方程。

算法：

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

• 返回值为gcd(a, b)，顺便求回来
• x、y为引用参数，可被函数里面变化传出

扩展理解

1、扩展欧几里得证明

对于方程： a*x + b*y = gcd(a, b)，假设a>b
根据欧几里得算法有 gcd(a, b) = gcd(b, a%b) = ... = gcd(r, 0)

对于gcd(b, a%b)：也有对应的解 b*x' + (a%b)*y' = gcd(b, a%b)
由于a%b = a - a/b*b，代入上面的方程，有：

b*x' + (a-a/b*b)*y = a*y' + b*(x'-a/b*y') = gcd(b, a%b)
与原方程 a*x + b*y = gcd(a, b)对比，根据方程式恒等原理，有：
x = y'
y = x' - a/b*y'

以上形成了递推关系，同时，对于最后的gcd(r, 0)，可以确定：
r*x + 0*y = gcd(r, 0) = r的一组解为： x=1, y = 0

因此可从这组解再往回递推，直到gcd(a, b)。

2、通解公式

如果ax+by=gcd(a, b)有解(x0, y0)，则通解公式为：

x = x0 + b/gcd(a, b) * t
y = y0 - a/gcd(a, b) * t

如果ax+by = k，gcd(a, b) | k，则：先求得ax+by = gcd(a,b)的解(x0, y0)，乘以k/gcd(a, b)，有：

x0' = x0 * k/gcd(a, b)
y0' = y0 * k/gcd(a, b)

然后就是一样的通解方程：

x = x0' + b/gcd(a, b) * t
y = y0' - a/gcd(a, b) * t