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

点击量：99

〇、前言

    以前扩展欧几里得推过几次，但是总是推不懂，理解起来非常费劲。快联赛了想起来有一道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|\)的最小值就是\(\text{lcm}(a,b)=ab\)，此时若\(ax’=p,by’=p\)，那么\(\Delta x\)就是\(p/a=b\)，\(\Delta y\)就是\(p/b=a\)了。

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

    对于\(ax+by=c,\gcd(a,b)|c\)的情况，只需要对原来的解乘上一个\(c/d\)就可以了。还是先求出\(ax+by=d\)的特解，而上面的\(p\)变成了\(\text{lcm}(a,b)=\frac{ab}c\)，此时\(\Delta x=p/a=\frac bc,\Delta y=p/b=\frac ac\)。然后把解都扩大\(c/d\)倍，即

\[\left\{\begin{matrix}
x=\frac cd x_0+k \frac bc \frac cd,\\
y=\frac cd y_0-k \frac ac \frac cd
\end{matrix}\right.,k\in \bf{Z}\]

\[\left\{\begin{matrix}
x=\frac cd x_0+k \frac bd,\\
y=\frac cd y_0-k \frac ad
\end{matrix}\right.,k\in \bf{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\bmod b\)转化为\(ax+by=1,y\in \bf {Z}\)，求这个方程的通解中的最小正整数。

    这里的\(d=1\)，不用做任何处理，直接调用\(\tt exgcd\)算法，得到特解\((x_0,y_0)\)，代入上面的通解，通解是

\[\left\{\begin{matrix}
x=x_0+kb,\\
y=y_0-ka
\end{matrix}\right.k\in \bf{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;
}