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

点击量：258

负一、upd on 2019.3.20

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

〇、前言

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

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

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

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

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

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

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

二、扩展欧几里得（exgcd）

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

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

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

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

上面交换了 $latex a,b$ 的位置，就是为了使 $latex x$ 的系数大于 $latex y$ 的系数，这样才能有下一步的“$latex a\%b$”。这样在 $latex a$ 和 $latex b$不断缩小的过程中，在某次得到 $latex b|a$，那么在下一次就会得到 $latex bx+(a\%b)y=d$，因为 $latex a\%b=0$，所以 $latex bx=d$，而这里的 $latex b$ 是开始算法前的 $latex \gcd(a,b)$，等于等式右边的 $latex d$，此时再令 $latex x=1$ 即可。然后就可以回溯了，对于 $latex 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’
$$
因此回溯的过程中把下一层的 $latex x,y$ 带出来，用 $latex a,b$ 的值修改这一层的 $latex x,y$，带回到上一层即可。

三、方程的通解

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

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

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

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

一般来说，用 exgcd 求出 $latex ax+by=c,\ \gcd(a,b)|c$ 的特解 $latex (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}
$$

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

题目描述

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

输入输出格式

输入格式：

一行，包含两个正整数 $latex a,b$，用一个空格隔开。

输出格式：

一个正整数 $latex x_0$，即最小正整数解。输入数据保证一定有解。

输入输出样例

输入样例#1：

3 10

输出样例#1：

7

说明

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

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

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

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

这里的 $latex d=1$，不用做任何处理，直接调用 exgcd 算法，得到特解 $latex (x_0,y_0)$，代入上面的通解，通解是
$$
\left\{\begin{matrix}
x=x_0+kb,\\
y=y_0-ka
\end{matrix}\right.k\in \mathbb{Z}
$$
然后直接对得到的 $latex x$ 对 $latex 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;
}