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

点击量：484

负一、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;
}