欧几里得及扩展欧几里得算法【学习笔记】【数学】【同余】

点击量：135

负一、upd on 2019.3.20

学 CRT 的时候发现了求通解时候的一个小问题。改起来有点麻烦，于是顺便把 html 代码全改成了 md……

〇、前言

以前扩展欧几里得推过几次，但是总是推不懂，理解起来非常费劲。快联赛了想起来有一道NOIp2012提高组 – 同余方程，感觉可以练一下exgcd，没想到不会写了……就想上网找个通俗好记的推导，然后找到了这一篇拓展欧几里得小结 – life_bre，感觉自己突然就懂了。

一、欧几里得算法（辗转相除法）

欧几里得算法可以用来在 \(O(\log n)\) 的复杂度内求出两个数的最大公约数。

辗转相除实际上是更相减损术的加速版，辗转相除法就是在不停对两个数取余，直到某次余数为 \(0\)。

令两个数为 \(a\) 和 \(b\)，若 \(b|a\)，则说明 \(b\) 就是两数的最大公约数；否则 \(a\) 可以表示为 \(k\times b+r(r<b)\).

因此设 \(\gcd(a,b)=t\)，那么 \(a=a’t,b=b’t\)，因此 \(r=r’t\)。

因为 \(r<b\)，所以不会产生更大的 \(t\)，因此\(\gcd(a,b)=\gcd(b,r)=t\)，而 \(r\) 就是 \(a\% b\)，因此可以递归下去直到 \(b|a\)。

二、扩展欧几里得（exgcd）

扩展欧几里得是用来求 \(ax+by=d,\gcd(a,b)|d\) 的特解的一种算法，我们现在只考虑 \(ax+by=d=\gcd(a,b)\)。

由 \(B\acute{e}zout\) 定理可知当 \(d=\gcd(a,b)\) 时，一定存在一组 \((x,y)\) 使得这个式子成立。

那么我们套用类似欧几里得算法的步骤，对于 \(bx’+(a\%b)y’=d\) 也一定存在一组 \((x’,y’)\)，使得式子成立。

既然两个式子右边都是 \(d\)，我们进行等量代换，得到 \(ax+by=bx’+(a\%b)y’\)。

上面交换了 \(a,b\) 的位置，就是为了使 \(x\) 的系数大于 \(y\) 的系数，这样才能有下一步的“\(a\%b\)”。这样在 \(a\) 和 \(b\)不断缩小的过程中，在某次得到 \(b|a\)，那么在下一次就会得到 \(bx+(a\%b)y=d\)，因为 \(a\%b=0\)，所以 \(bx=d\)，而这里的 \(b\) 是开始算法前的 \(\gcd(a,b)\)，等于等式右边的 \(d\)，此时再令 \(x=1\) 即可。然后就可以回溯了，对于 \(ax+by=bx’+(a\%b)y’\) 这个方程，我们把取模改成定义式
$$
a\%b=a-b\left\lfloor\frac ab\right\rfloor
$$
得到
$$
ax+by=bx’+(a-b\left\lfloor\frac ab\right\rfloor)y’\ ax+by=bx’+ay’-b\left\lfloor\frac ab\right\rfloor y’
$$
移项得
$$
a(x-y’)-b(x’-y-\left\lfloor\frac ab\right\rfloor y’)=0
$$
我们要消掉 $a,b$ 两项，就要使
$$
x=y’,y=x’-\left\lfloor\frac ab\right\rfloor y’
$$
因此回溯的过程中把下一层的 \(x,y\) 带出来，用 \(a,b\) 的值修改这一层的 \(x,y\)，带回到上一层即可。

三、方程的通解

对于 \(ax+by=d=\gcd(a,b)\)，如何让 \(ax\) 减去一个整数，\(by\) 加上一个整数，且这两个整数相等呢？

这个相等的整数 \(p\) 一定保证了 \(a|p,b|p\)，因此 \(|p|(p>0)\) 的最小值就是 \(\text{lcm}(a,b)\)，此时若 \(ax’=p,by’=p\)，那么\(\Delta x\) 就是 \(p/a=\frac b{\gcd(a,b)}\)，\(\Delta y\) 就是 \(p/b=\frac a{\gcd(a,b)}\) 了。

如果令特解为 \((x_0,y_0)\)，那么 \(x=x_0+k\frac b{\gcd(a,b)},y=y_0-k\frac a{\gcd(a,b)},k\in \mathbb{Z}\) 就是方程的通解。

对于 \(ax+by=c,\gcd(a,b)|c\) 的情况，还是先求出 \(ax+by=d\) 的特解 \((x_0,y_0)\)，两边同乘 \(\frac cd\)，则得出原方程特解 \((x_1,y_1)\)。此时 \(c\) 实际上是没有影响的，所以通解是 \(x=x_1+k\frac b{\gcd(a,b)},y=y_1-k\frac a{\gcd(a,b)},k\in \mathbb{Z}\)。

一般来说，用 exgcd 求出 \(ax+by=c,\ \gcd(a,b)|c\) 的特解 \((x_0,y_0)\) 就能找到这个方程组的通解了。
$$
\left\{\begin{matrix}
x=\frac cd x_0+k \frac bd,\\
y=\frac cd y_0-k \frac ad
\end{matrix}\right.,k\in \mathbb{Z}
$$

四、同余方程，出来挨打！

题目描述

求关于 \(x\) 的同余方程 \(ax\equiv 1\pmod b\) 的最小正整数解。

输入输出格式

输入格式：

一行，包含两个正整数 \(a,b\)，用一个空格隔开。

输出格式：

一个正整数 \(x_0\)，即最小正整数解。输入数据保证一定有解。

输入输出样例

输入样例#1：

3 10

输出样例#1：

7

说明

对于 \(40\%\) 的数据，\(2\le b\le 1,000\)；

对于 \(60\%\) 的数据，\(2\le b\le 50,000,000\)；

对于 \(100\%\) 的数据，\(2\le a,b\le 2,000,000,000\)。

我们把题目中的 \(ax\equiv 1\pmod b\) 转化为 \(ax+by=1,y\in \mathbb{Z}\)，求这个方程的通解中的最小正整数。

这里的 \(d=1\)，不用做任何处理，直接调用 exgcd 算法，得到特解 \((x_0,y_0)\)，代入上面的通解，通解是
$$
\left\{\begin{matrix}
x=x_0+kb,\\
y=y_0-ka
\end{matrix}\right.k\in \mathbb{Z}
$$
然后直接对得到的 \(x\) 对 \(b\) 取模处理即可。

Code：

#include<cstdio>
#include<cstring>
#define ll long long
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b)
    {
        x=1;
        y=0;
        return a;
    }
    ll d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int main()
{
    ll a,b,x,y;
    scanf("%lld%lld",&a,&b);
    exgcd(a,b,x,y);
    printf("%lld\n",(x%b+b)%b);
    return 0;
}