同余问题(一)——扩展欧几里得exgcd

时间:2021-01-16 15:32:20

前言

扩展欧几里得算法是一个很好的解决同余问题的算法,非常实用。

欧几里得算法

简介

欧几里得算法,又称辗转相除法。

主要用途

求最大公因数\(gcd\)。

公式

\(gcd(a,b)=gcd(b,a\%b)\)

公式证明

\(a\)可以表示成\(a=kb+a\%b\)(\(k\)为自然数)。

假设\(g\)是\(a,b\)的一个公约数,则有\(g|a, g|b\)。

\(\because a\%b=a-kb\),

\(\therefore g|(a\%b),\therefore g\)是\(b,a\%b\)的公约数。

综上所述,\(a,b\)和\(b,a\%b\)的公约数是一样的,其\(gcd\)也必然相等。

代码实现

inline int gcd(int x,int y) {return y?gcd(y,x%y):x;}

扩展欧几里得算法

简介

扩展欧几里得建立于欧几里得算法的基础上。(该算法的升级版 徐xgcd有待XuRuiYang奆佬发明)

主要用途

对于已知a,b求解x,y使其满足ax+by=gcd(a,b)。

解法

我们可以对\((a,b)\)不断辗转相除。

根据欧几里得算法,最后剩下的两个数一定为\((gcd(a,b),0)\),

显然,此时\(x=1,y=0\)是原式的一组解。

现在,我们需要考虑,若已知\((b,a\%b)\)的解,如何推出\((a,b)\)的解。

设\(x_0,y_0\)为\((b,a\%b)\)的一组解,则\(x_0·b+y_0(a\%b)=gcd(b,a\%b)\)。

将这个式子转化一下,可以得到\(x_0·b+y_0(a-\lfloor\frac ab\rfloor*b)=gcd(a,b)\)。

去括号,得\(x_0·b+y_0·a-(y_0·\lfloor\frac ab\rfloor)·b=gcd(a,b)\)。

合并同类项,得\(y_0·a+(x_0-y_0·\lfloor\frac ab\rfloor)·b=gcd(a,b)\)。

\(\therefore x=y_0,y=x_0-y_0·\lfloor\frac ab\rfloor\)是原式的一组解。

递归即可。

代码实现

inline int exgcd(int x,int y,int &s1,int &s2)
{
if(!y) return s1=1,s2=0,x;
register int res=exgcd(y,x%y,s2,s1);
return s2-=x/y*s1,res;
}

扩欧的典型应用:求乘法逆元

关于乘法逆元可以看看这篇博客:浅谈乘法逆元的三种解法