6.7 KiB
一、欧几里德定理
欧几里德定理： gcd(a, b) = gcd(b , a\%b)
欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。
他避免了我们去枚举a，b的因子，让我们可以在几乎是 log 的时间复杂度里求解出来 a 和 b 的最大公约数。
基于以上定理，我们就可以很轻松求出，a和b的最大公因数，对于一般的欧几里得算法就不再都说什么了，模板：
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。即上述定理所说的，两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。
二、裴蜀定理
裴蜀定理（或贝祖定理）得名于法国数学家艾蒂安·裴蜀，说明了对任何整数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的，所以没有整数解!
三、求贝祖数(特解)
什么是贝祖数？
比如：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呢？因为 普遍意义上的求贝祖数，一般是指不小于零的一组解 ，那么不小于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′ 再利用上述公式回代即可
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、求解不定方程
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 输出最小正整数解