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

作者: wjyyy 分类: gcd/lcm,同余,学习笔记,数学 发布时间: 2018-10-26 16:57

点击量:62

〇、前言

    以前扩展欧几里得推过几次,但是总是推不懂,理解起来非常费劲。快联赛了想起来有一道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;
}

2
说点什么

avatar
1 Comment threads
1 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
wjyyyMayflyyh Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
Mayflyyh
游客

大佬可以加下QQ吗?

/* */