## 6.2 特解与通解

### 6.2.1 特解推导过程

我们需要求解形如以下方程的整数解：
$$a \cdot x + b \cdot y = \gcd(a, b)$$
只要解出这组解，对于更一般的方程 $a \cdot x + b \cdot y = c$，只需将解扩大 $c / \gcd(a, b)$ 倍即可得到原方程的解。

#### 1. 从辗转相减法观察
观察到该式子的本质是 $a$ 和 $b$ 辗转相减的过程。按照计算机递归思维，我们可以先缩小问题的规模。
假设我们已经求出了规模更小的子问题 $(a - b) \cdot x_1 + b \cdot y_1 = \gcd(a, b)$ 的解 $x_1, y_1$。

将该式变形：
$$a \cdot x_1 - b \cdot x_1 + b \cdot y_1 = \gcd(a, b)$$
$$a \cdot x_1 + b \cdot (y_1 - x_1) = \gcd(a, b)$$

对照原方程 $a \cdot x + b \cdot y = \gcd(a, b)$，可以得到原问题的解为：
$$x = x_1, \quad y = y_1 - x_1$$

#### 2. 推广到辗转相除法
为了提高效率，我们可以用辗转相除来代替辗转相减。根据欧几里得算法：$\gcd(a, b) = \gcd(b, a \bmod b)$。
现在假设我们已经求出了下一层子问题的解 $x_1, y_1$：
$$b \cdot x_1 + (a \bmod b) \cdot y_1 = \gcd(a, b)$$

由带余除法可知：$a \bmod b = a - \lfloor a/b \rfloor \cdot b$。
代入上式得：
$$b \cdot x_1 + (a - \lfloor a/b \rfloor \cdot b) \cdot y_1 = \gcd(a, b)$$

整理合并同类项（按 $a$ 和 $b$ 分组）：
$$a \cdot y_1 + b \cdot (x_1 - \lfloor a/b \rfloor \cdot y_1) = \gcd(a, b)$$

对照原方程 $a \cdot x + b \cdot y = \gcd(a, b)$，可以得到当前层的解映射关系：
$$x = y_1, \quad y = x_1 - \lfloor a/b \rfloor \cdot y_1$$

#### 3. 递归边界
通过不断缩小规模，问题最终会到达边界：
$$\gcd(a, b) \cdot x + 0 \cdot y = \gcd(a, b)$$
此时，$b = 0$，显然可以得到一组特解：
$$(x, y) = (1, 0)$$

#### 6.2.3 代码实现扩展欧几里得
```
int extgcd(int a, int b, int &x, int &y)
{
  if(!b){
    x = 1 , y = 0;
    return a;//返回最大公约数

}
  int d = extgcd(b, a%b, x, y); //此时的x和y相当于x1和y1
    x-=a/b * y;
    std::swap(x,y);

return d ;
}
```

以下是将图片内容整理并优化逻辑后的 Markdown 格式讲义：

---

### 6.2.4 通解

当扩展欧几里得算法执行完毕后，我们得到的是方程 $a \cdot x + b \cdot y = \gcd(a, b)$ 的一组**特解** $(x, y)$。

#### 1. 变化规律推导
通解的变化规律在于：$x$ 和 $y$ 的值向**相反方向变化**（例如 $x$ 变大，$y$ 变小），使得等式左边的增量与减量相互抵消，保持结果依然等于 $\gcd(a, b)$。

设 $x$ 和 $y$ 变化的最小单位值分别为 $d_1$ 和 $d_2$，则应满足：
$$a \cdot (x + d_1) + b \cdot (y - d_2) = \gcd(a, b)$$

展开并消去原有的 $a \cdot x + b \cdot y = \gcd(a, b)$，可得：
$$a \cdot d_1 = b \cdot d_2$$

#### 2. 最小单位值的确定
为求得变化的最小单位，我们将等式两边同时除以 $\gcd(a, b)$。令：
$$k_1 = \frac{a}{\gcd(a, b)}, \quad k_2 = \frac{b}{\gcd(a, b)}$$

代入上式得：
$$k_1 \cdot d_1 = k_2 \cdot d_2$$

由于 $k_1$ 与 $k_2$ 互质（已除去最大公约数），根据数论性质，要使等式成立且 $d_1, d_2$ 为最小正整数，必然有：
$$d_1 = k_2 = \frac{b}{\gcd(a, b)}, \quad d_2 = k_1 = \frac{a}{\gcd(a, b)}$$

#### 3. 通解公式
由上述推导可得，方程的所有整数解（通解）可以表示为：
$$(x + k \cdot d_1, y - k \cdot d_2)$$
即：
$$\left(x + k \cdot \frac{b}{\gcd(a, b)}, \quad y - k \cdot \frac{a}{\gcd(a, b)}\right), \quad k \in \mathbb{Z}$$

#### 4. 示例说明
根据之前 6.2.2 的例子：
已知 $a = 13, b = 8, \gcd(a, b) = 1$，求得一组特解为：
$$x = -3, \quad y = 5$$

代入通解公式，得到该方程的通解为：
$$(-3 + 8k, \quad 5 - 13k), \quad k \in \mathbb{Z}$$

6.2 特解与通解

6.2.1 特解推导过程

我们需要求解形如以下方程的整数解： $$a \cdot x + b \cdot y = \gcd(a, b)$$ 只要解出这组解，对于更一般的方程 $a \cdot x + b \cdot y = c$，只需将解扩大 $c / \gcd(a, b)$ 倍即可得到原方程的解。

1. 从辗转相减法观察

观察到该式子的本质是 $a$ 和 $b$ 辗转相减的过程。按照计算机递归思维，我们可以先缩小问题的规模。假设我们已经求出了规模更小的子问题 $(a - b) \cdot x_1 + b \cdot y_1 = \gcd(a, b)$ 的解 $x_1, y_1$。

将该式变形： $$a \cdot x_1 - b \cdot x_1 + b \cdot y_1 = \gcd(a, b)$$ $$a \cdot x_1 + b \cdot (y_1 - x_1) = \gcd(a, b)$$

对照原方程 $a \cdot x + b \cdot y = \gcd(a, b)$，可以得到原问题的解为： $$x = x_1, \quad y = y_1 - x_1$$

2. 推广到辗转相除法

为了提高效率，我们可以用辗转相除来代替辗转相减。根据欧几里得算法：$\gcd(a, b) = \gcd(b, a \bmod b)$。现在假设我们已经求出了下一层子问题的解 $x_1, y_1$： $$b \cdot x_1 + (a \bmod b) \cdot y_1 = \gcd(a, b)$$

由带余除法可知：$a \bmod b = a - \lfloor a/b \rfloor \cdot b$。代入上式得： $$b \cdot x_1 + (a - \lfloor a/b \rfloor \cdot b) \cdot y_1 = \gcd(a, b)$$

整理合并同类项（按 $a$ 和 $b$ 分组）： $$a \cdot y_1 + b \cdot (x_1 - \lfloor a/b \rfloor \cdot y_1) = \gcd(a, b)$$

对照原方程 $a \cdot x + b \cdot y = \gcd(a, b)$，可以得到当前层的解映射关系： $$x = y_1, \quad y = x_1 - \lfloor a/b \rfloor \cdot y_1$$

3. 递归边界

通过不断缩小规模，问题最终会到达边界： $$\gcd(a, b) \cdot x + 0 \cdot y = \gcd(a, b)$$ 此时，$b = 0$，显然可以得到一组特解： $$(x, y) = (1, 0)$$

6.2.3 代码实现扩展欧几里得

int extgcd(int a, int b, int &x, int &y)
{
  if(!b){
    x = 1 , y = 0;
    return a;//返回最大公约数

  }
  int d = extgcd(b, a%b, x, y); //此时的x和y相当于x1和y1
    x-=a/b * y;
    std::swap(x,y);

  return d ;
}

以下是将图片内容整理并优化逻辑后的 Markdown 格式讲义：

6.2.4 通解

当扩展欧几里得算法执行完毕后，我们得到的是方程 $a \cdot x + b \cdot y = \gcd(a, b)$ 的一组特解 $(x, y)$。

1. 变化规律推导

通解的变化规律在于：$x$ 和 $y$ 的值向相反方向变化（例如 $x$ 变大，$y$ 变小），使得等式左边的增量与减量相互抵消，保持结果依然等于 $\gcd(a, b)$。

设 $x$ 和 $y$ 变化的最小单位值分别为 $d_1$ 和 $d_2$，则应满足： $$a \cdot (x + d_1) + b \cdot (y - d_2) = \gcd(a, b)$$

展开并消去原有的 $a \cdot x + b \cdot y = \gcd(a, b)$，可得： $$a \cdot d_1 = b \cdot d_2$$

2. 最小单位值的确定

为求得变化的最小单位，我们将等式两边同时除以 $\gcd(a, b)$。令： $$k_1 = \frac{a}{\gcd(a, b)}, \quad k_2 = \frac{b}{\gcd(a, b)}$$

代入上式得： $$k_1 \cdot d_1 = k_2 \cdot d_2$$

由于 $k_1$ 与 $k_2$ 互质（已除去最大公约数），根据数论性质，要使等式成立且 $d_1, d_2$ 为最小正整数，必然有： $$d_1 = k_2 = \frac{b}{\gcd(a, b)}, \quad d_2 = k_1 = \frac{a}{\gcd(a, b)}$$

3. 通解公式

由上述推导可得，方程的所有整数解（通解）可以表示为： $$(x + k \cdot d_1, y - k \cdot d_2)$$ 即： $$\left(x + k \cdot \frac{b}{\gcd(a, b)}, \quad y - k \cdot \frac{a}{\gcd(a, b)}\right), \quad k \in \mathbb{Z}$$

4. 示例说明

根据之前 6.2.2 的例子：已知 $a = 13, b = 8, \gcd(a, b) = 1$，求得一组特解为： $$x = -3, \quad y = 5$$

代入通解公式，得到该方程的通解为： $$(-3 + 8k, \quad 5 - 13k), \quad k \in \mathbb{Z}$$

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com

特解与通解、线性同余方程