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

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

点击量:209

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

4
说点什么

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

大佬可以加下QQ吗?

trackback

[…] 【exgcd学习笔记】 […]

trackback

[…] 我之前写过的 exgcd 学习笔记 […]

/* */