欧几里得及扩展欧几里得算法【学习笔记】【数学】【同余】
点击量:221
负一、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;
}
大佬可以加下QQ吗?
没有大佬。
[…] 【exgcd学习笔记】 […]
[…] 我之前写过的 exgcd 学习笔记 […]