|
|
|
|
|
### 一、欧几里德定理
|
|
|
欧几里德定理： $gcd(a, b) = gcd(b , a\%b)$
|
|
|
|
|
|
欧几里德算法又称辗转相除法，**用于计算两个整数$a,b$的最大公约数**。
|
|
|
|
|
|
他避免了我们去枚举$a，b$的因子，让我们可以在几乎是 $log$ 的时间复杂度里求解出来 $a$ 和 $b$ 的**最大公约数**。
|
|
|
|
|
|
基于以上定理，我们就可以很轻松求出，$a$和$b$的最大公因数，对于一般的欧几里得算法就不再都说什么了，模板：
|
|
|
```c++
|
|
|
int gcd(int a,int b){
|
|
|
return b?gcd(b,a%b):a;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
**证明**：
|
|
|
设 $a>b$
|
|
|
令 $c=a\%b$
|
|
|
可得：$a=k*b+c$ ($k$最小是$1$,$c$肯定小于$b$)
|
|
|
|
|
|
如果$c$为$b$的一个约数，即$b\%c=0$
|
|
|
则$c$也一定$a$的约数，因为$a\%c=(k*b+c)\%c=0$
|
|
|
这时，$c$即为$a$和$b$的最大公约数。
|
|
|
|
|
|
如果$c$不为$b$的约数，设$b\%c=d$
|
|
|
同理，如果$d$是$c$的一个因数，那$d$也一定是$a、b$的因数
|
|
|
重复上诉操作，直至求出一个满足条件的数，即为所求。
|
|
|
|
|
|
|
|
|
**举栗子**：
|
|
|
以求 $46$ 与 $28$ 的最大公约数为例：
|
|
|
|
|
|
第一次迭代, $a = 44, b = 28$, 较小数为 $28$, 余数为 $16$。
|
|
|
第二次迭代, $a = 28, b = 16$, 较小数为 $16$, 余数为 $12$。
|
|
|
第三次迭代, $a = 16, b = 12$, 较小数为 $12$, 余数为 $4$。
|
|
|
第四次迭代, $a = 12, b = 4$, 较小数为 $4$, 余数为 $0$。
|
|
|
第五次迭代, $a = 4, b = 0$, 因为$0$能被任何整数整除，易得$4$和$0$的最大公约数为$4$，算法结束。
|
|
|
|
|
|
观察每次迭代的$a$ 和 $b$, 不难发现, $<44,28>$, $<28,16>$ , $<16,12>$ , $<12,4>$的最大公约数都是$4$。即上述定理所说的，两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。
|
|
|
|
|
|
|
|
|
### 二、[裴蜀定理](https://baike.baidu.com/item/%E8%A3%B4%E8%9C%80%E5%AE%9A%E7%90%86/5186593?fr=aladdin)
|
|
|
|
|
|
裴蜀定理（或贝祖定理）得名于法国数学家艾蒂安·裴蜀，说明了对任何整数$a$、$b$和它们的最大公约数$d$，关于未知数$x$和$y$的线性不定方程（称为裴蜀等式）：若$a$,$b$是整数,且$gcd(a,b)=d$，那么**对于任意的整数$x$,$y$,$ax+by$都一定是$d$的倍数，特别地，一定存在整数$x$,$y$，使$ax+by=d$成立**。
|
|
|
|
|
|
**推论：$a$,$b$互质的充分必要条件是存在整数$x$,$y$使$ax+by=1$。**
|
|
|
|
|
|
|
|
|
**举栗子**：
|
|
|
$2x+y=3$
|
|
|
|
|
|
那么$a=2$,$b=1$,$m=3$,$gcd(2,1)=1$,$3$是$1$的倍数，所以这个方程一定有整数解。
|
|
|
比如$x=1$,$y=1$就是一个整数解，还可以有$x=-2$,$y=7$也是一组整数解。
|
|
|
|
|
|
**注意：如果一个二元一次方程有正整数解，那么不只是一组解。**
|
|
|
|
|
|
**再举一个栗子**：
|
|
|
$4x+2y=5$
|
|
|
有没有整数解呢？没有，因为$a=4,b=2,m=5,gcd(4,2)=2,5$是除不开$2$的，所以没有整数解!
|
|
|
|
|
|
|
|
|
### 三、[求贝祖数(特解)](https://www.bilibili.com/video/av77974575/)
|
|
|
什么是贝祖数？
|
|
|
比如：$2x+y=3$，那么符合这个等式的$x=1$,$y=1$就是一组贝祖数。
|
|
|
|
|
|
在计算机算法中，可以使用**扩展欧几里得算法求贝祖数**。
|
|
|
|
|
|
举个栗子：
|
|
|
求 $104x+40y=8$ ，有没有合适的$x,y$,也就是求贝祖数。
|
|
|
|
|
|
通过贝祖定理看一下，它是不是有解： $gcd(104,40)=8$,$8$是$8$的倍数，所以此方程一定有解，那么解是什么呢？
|
|
|
|
|
|
|
|
|
|
|
|
**扩展欧几里得算法的推导过程：**
|
|
|
|
|
|
我们先来求方程 $ax+by=gcd(a,b)$的解
|
|
|
|
|
|
($1$)、当 $b=0$时
|
|
|
|
|
|
$ax+by=gcd(a,0)$，也就是:$ax=gcd(a,0)=a$,所以$x=1$。
|
|
|
|
|
|
那么$y$呢？因为 <font color='red'><b>普遍意义上的求贝祖数，一般是指不小于零的一组解</b></font> ，那么不小于$0$的第一个可能$y$值就是:$y=0$,所以，可以将$x=1,y=0$做为一组**特解**返回，也就是返回了一组**不小于零的贝祖数**。
|
|
|
|
|
|
($2$)、当 $b≠0$时
|
|
|
|
|
|
$\because gcd(a,b)=gcd(b,a\%b)$
|
|
|
|
|
|
并且$①\ \ \ \ ax+by=gcd(a,b)$
|
|
|
|
|
|
$\therefore bx′+(a\%b)y′=gcd(a,b)$
|
|
|
|
|
|
$\because a−⌊a/b⌋∗b=a\%b$
|
|
|
|
|
|
$\therefore bx′+(a−⌊a/b⌋∗b)y′=gcd(a,b)$
|
|
|
|
|
|
变形一下：
|
|
|
|
|
|
$② \ \ \ \ ay′+b(x′−⌊a/b⌋∗y′)=gcd(a,b)$
|
|
|
|
|
|
对比$① ②$系数：
|
|
|
|
|
|
$\therefore$ $x=y′,y=x′−⌊a/b⌋∗y′$
|
|
|
|
|
|
因此可以采取递归算法 先求出下一层的$x′$和$y′$ 再利用上述公式回代即可
|
|
|
|
|
|
```c++
|
|
|
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;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
|
|
|
### 四、通解公式
|
|
|
|
|
|
有了上面求出的特解，我们就可以得到通解公式：
|
|
|
|
|
|
$a*x+b*y=c$ ①
|
|
|
$a*x_0+b*y_0=c$ ②
|
|
|
|
|
|
联立得到：
|
|
|
$a*(x-x_0)=b*(y_0-y)$
|
|
|
|
|
|
等式两边同时除以$gcd(a,b)$得到：
|
|
|
|
|
|
$\displaystyle \frac{a}{gcd(a,b)}*(x-x_0)=\frac{b}{gcd(a,b)}*(y_0-y)$
|
|
|
|
|
|
我们知道，若有两个数$a$和$b$，他们同时除以**最大公约数**，之后的商是**互质**的。所以在上面等式中，如果成立，那么说明，$\displaystyle \frac{b}{gcd(a,b)}$一定是 $(x - x_0)$的倍数，而 $\displaystyle \frac{a}{gcd(a,b)}$ 一定是$(y_0-y)$的倍数。
|
|
|
|
|
|
所以 $\displaystyle x-x_0=\frac{b}{gcd(a,b)}*k$ , $\displaystyle y_0-y=\frac{a}{gcd(a,b)}*k$
|
|
|
|
|
|
所以 $$x=x_0+\frac{b}{gcd(a,b)}*k$$
|
|
|
$$y=y_0-\frac{a}{gcd(a,b)}*k$$
|
|
|
|
|
|
### 五、扩展欧几里德算法的应用
|
|
|
https://zhuanlan.zhihu.com/p/42707457
|
|
|
|
|
|
#### 1、求解不定方程
|
|
|
[AcWing 877. 扩展欧几里得算法](https://www.acwing.com/problem/content/879/)
|
|
|
|
|
|
[AcWing 203. 同余方程](https://www.acwing.com/problem/content/205/)
|
|
|
|
|
|
#### 2、求解线性同余方程
|
|
|
给我们$a,b,c$，让我们求一个整数$x$,使得$ax \equiv c (mod \ b)$。
|
|
|
|
|
|
就等价于 $ax-c$是$b$的整数倍，假设倍数是$y$,则有:$ax-c=by$
|
|
|
变形：$ax-by=c$,由于倍数是可正可负，所以可以认为把负号吃到变量$y$中，方程就是：
|
|
|
$$ax \equiv c (mod \ b) \Leftrightarrow ax+by=c$$
|
|
|
|
|
|
这玩意咋理解呢？我们可以想像一下生活中的例子，比如$1$号是星期一，那么$8$号也是星期一。因为一周有$7$天，$7$天一循环嘛。
|
|
|
此时 我们认为 $$1 \equiv 8 (mod \ 7)$$
|
|
|
|
|
|
说的再直白些，就是从一个大数当中，扣去循环节的整数倍，得到的余数与小数是相等的。
|
|
|
|
|
|
#### 3、求解模的逆元
|
|
|
|
|
|
练习题
|
|
|
POJ -1061青蛙的约会
|
|
|
https://blog.csdn.net/GD_ONE/article/details/96479556
|
|
|
|
|
|
luogu P5656
|
|
|
|
|
|
同余方程、青蛙的约会、最幸运的数字
|
|
|
|
|
|
一.一元线性同余方程
|
|
|
poj 1061 2115 2142
|
|
|
|
|
|
二.一元线性同余方程组
|
|
|
先看一篇博客
|
|
|
对于模线性方程组，可以进行两两合并，求出方程的最终解。
|
|
|
poj 2891 (最小正整数解）
|
|
|
|
|
|
hdu 1573
|
|
|
求一定范围内的解的个数
|
|
|
|
|
|
hdu3579
|
|
|
输出最小正整数解
|
|
|
|
