文章目录

数论基础——扩展欧几里得算法（模板）欧几里得算法原理代码扩展欧几里得算法原理代码应用

数论基础——扩展欧几里得算法（模板）

欧几里得算法

原理

设gcd(a,b)是计算自然数a和b得最大公约数得函数，令a=b×p+q（a>b）a=b\times p+q（a>b）a=b×p+q（a>b）

则gcd(b,q)既整除a又整除b，也就是整除gcd(a,b)。

反之，因为q=a−b×pq=a-b\times pq=a−b×p，同理得gcd(a,b)整除gcd(b,q)。

因此可得：gcd(a,b)=gcd(b,a%b)gcd(a,b)=gcd(b,a\%b)gcd(a,b)=gcd(b,a%b)

反复操作，最终得到gcd(a,b)=gcd(c,0)=cgcd(a,b)=gcd(c,0)=cgcd(a,b)=gcd(c,0)=c

注：实际上就是辗转相除法。

代码

typedef long long LL;LL gcd(LL x,LL y){return y ? gcd(y,x%y) : x;}LL lcm(LL x,LL y){return x*y/gcd(x,y);}

扩展欧几里得算法

原理

1.设int exgcd(int a,int b,int &x, int &y)是求解方程a∗x+b∗y=gcd(a,b)a*x+b*y=gcd(a,b)a∗x+b∗y=gcd(a,b)的函数它的返回值是gcd(a,b)。

2.类比gcd函数，我们可以递归定义exgcd。

由gcd(a,b)=ax+by和gcd(b,a%b)=bx’+(a%b)y’

可得：ax+by=bx’+(a%b)y’

代入：a%b=a-(a/b)b

得：ax+by=bx’+(a%b)y’=bx’+(a-(a/b)b)y’=ay’+b(x’-(a/b)y’)

因此要求x,y只需要得到x’,y’

而当b=0时，a1+b0=gcd(a,b)（递归结束条件）

代码

int exgcd(int a,int b,int &x, int &y){int d=a;if(!b){x=1;y=0;return d;}d=exgcd(b,a%b,y,x);y-=(a/b)*x;}

应用

1.求解不定方程（实际上直接枚举也可以得到答案）；

2.求解线性同余方程；

3.求解模的逆元；