Acwing-基础算法课笔记之数学知识（扩展欧几里得算法）

一、扩展欧几里得算法

1、裴蜀定理

对于任意正整数 $a$，$b$，那么一定存在非零整数 $x$，$y$，使得 $ax+by=exgcd(a,b)$

2、过程模拟

例如求 $gcd(a,b)$

$\bullet$当 $b=0$ 时，则可以直接返回 $a$ 的值，即最大公约数，推理如下：

根据公式$ax+by=exgcd(a,b)$，得：

$a\times x+0\times y=a$

$\iff a\times x=a$

$\iff x=1$

$\Rightarrow y=0$

$\bullet$当 $b\ne 0$ 时，求得扩展欧几里得算法$exgcd(b,a\%b,y,x)$，推理如下：

$by+(a$ $mod$ $b)x=exgcd(a,b)$

$\Rightarrow a$ $mod$ $b=a-\lfloor \frac{a}{b}\rfloor b$

$\Rightarrow by+(a-\lfloor \frac{a}{b}\rfloor b)x=exgcd(a,b)$

$\Rightarrow ax+b(y-\lfloor \frac{a}{b}\rfloor x)=exgcd(a,b)$

3、代码模板

// 求x, y，使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y)
{if (!b){x = 1; y = 0;return a;}int d = exgcd(b, a % b, y, x);y -= (a/b) * x;return d;
}

Acwing-扩展欧几里得算法

二、线性同余方程

1、定义

给定 $n$ 组数据 $a_i$，$b_i$，$m_i$，对于每组数求出一个 $x_i$，使其满足 $a_i\times x_i\equiv b_i(mod$ $m_i)$。

2、模拟过程

设 $a=2$，$b=3$，$m=6$，此时以上并不满足条件。

设 $a=4$，$b=3$，$m=5$，要使 $4x\%5=3$，所以$x=-3$或$x=2$

3、结论证明

$a\times x\equiv b(mod$ $m)$

$\iff$$\exists y\in Z$，使得$ax=my+b$

$\iff ax-my=b$

$\iff y^{\prime }=-y$

$\iff ax+m{y}^{\prime }=gcd(a,m)$（条件：$gcd(a,m)|b$）