北京企业建站团队/微信小程序开发零基础入门

欧几里得算法

• 百度一下

• 人物介绍

在欧几里得著的《几何原本》里面，有用线段的划分来讲解这个数学方法的，这里我们从代数而不是几何上来讲，并且侧重于算法OI竞赛。

欧几里得算法（$gcd$），又称辗转相除法，可以用来快速计算两个整数的最大公约数，并有许多扩展应用。

---

下面我们来看公式:
$$gcd(n,m)=gcd(m,n\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{m})$$

我们可以简单的证明一下这个公式的正确性:
我们令$g=gcd(n,m)$，那么显然$g|n,g|m$（$a|b$表示$a$为$b$的因子）。又因为n mod m=n−m×⌊nm⌋n\ \rm mod\ m=n-m\times \lfloor\frac{n}{m}\rfloorn mod m=n−m×⌊mn​⌋，那么我们可以将$n,m$写为n=k1g,m=k2gn=k_1g,m=k_2gn=k1​g,m=k2​g，那么n mod m=n−m×⌊nm⌋=k1g−k2g⌊k1gk2g⌋=g(k1−k2⌊k1gk2g⌋)n\ \rm mod\ m=n-m\times \lfloor\frac{n}{m}\rfloor=k_1g-k_2g\lfloor\frac{k_1g}{k_2g}\rfloor=g\left(k_1-k_2\left\lfloor\frac{k_1g}{k_2g}\right\rfloor\right)n mod m=n−m×⌊mn​⌋=k1​g−k2​g⌊k2​gk1​g​⌋=g(k1​−k2​⌊k2​gk1​g​⌋)，而(k1−k2⌊k1gk2g⌋)\left(k_1-k_2\left\lfloor\frac{k_1g}{k_2g}\right\rfloor\right)(k1​−k2​⌊k2​gk1​g​⌋)肯定为整数，所以$g|(n\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{m})$，那么显然$g|gcd(m,n\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{m})$，(因为$g$为$n,m$的因子)。接下来我们令g^=gcd(m,n mod m)\hat g=gcd(m,n\ \rm mod\ m)g^​=gcd(m,n mod m)，那么显然有g^∣g\hat g|gg^​∣g，又因为前面我们可以得知g∣g^g|\hat gg∣g^​，所以就有g=g^g=\hat gg=g^​，那么$gcd(n,m)=gcd(m,n\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{m})$。

所以代码就简单啦!
递归边界为$m=0$时，因为模数不能为0，所以此时就可以直接返回$n$。

int gcd(int n,int m){if(!m) return n;else return gcd(m,n%m); 
}//也可以用自带的__gcd(n,m);

---

扩展欧几里得算法

• 前置

• 裴蜀定理（贝祖定理）

内容:对于一个系数为整数（$a,b,c$为整数）的二元一次方程$ax+by=c$，若其存在整数解，当且仅当$gcd(a,b)|c$。
用处:判断一个上述的二元一次方程是否有整数解。

简单的证明：
我们令$g=gcd(a,b)$，同样的我们可以将$a,b$写成a=k1g,b=k2ga=k_1g,b=k_2ga=k1​g,b=k2​g，那么显然ax+by=g(k1x+k2y)ax+by=g(k_1x+k_2y)ax+by=g(k1​x+k2​y)，所以$g|(ax+by)$。

所以当$gcd(a,b)|c$时必然有整数解，下面我们将在扩展欧几里得算法讲解给出证明，及其整数解的求法。

---

正题

• Exgcd

$ax+by=c$在$c|gcd(a,b)$前提下是否一定有整数解呢？

因为有了前提，所以我们可以将原式写成$ax+by=k\cdot gcd(a,b)$，由于$k$为整数，那么如果$ax+by=gcd(a,b)$有整数解，那么原式一定有整数解（倍数关系），那么只需证明并求出$ax+by=gcd(a,b)$的一组特殊解(x1,y1)(x_1,y_1)(x1​,y1​)，然后所有的解都可以表示出来（原来的解就是现在解的$k$倍）。

所以现在我们只需证明$ax+by=gcd(a,b)$有解即可。

通过$gcd$的递推式可知，我们如果的到如下式子的一组解：
$$bx+(a\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{b})\mathrm{y}=\mathrm{g}\mathrm{c}\mathrm{d}(\mathrm{b},\mathrm{a}\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{b})$$
令解为(x1,y1)(x_1,y_1)(x1​,y1​)，那么就有如下推导:
ax+by=bx1+(a mod b)y1ax+by=bx_1+(a\ \rm mod\ b)y_1ax+by=bx1​+(a mod b)y1​
=bx1+(a−⌊ab⌋×b)y1=bx_1+(a-\left\lfloor\frac{a}{b}\right\rfloor\times b)y_1=bx1​+(a−⌊ba​⌋×b)y1​
=ay1+(x1−⌊ab⌋y1)b=ay_1+(x_1-\left\lfloor\frac{a}{b}\right\rfloor y_1)b=ay1​+(x1​−⌊ba​⌋y1​)b
一个小引理当$ax+by=az+bk$，必然$x,y$有一组解为$x=z,y=k$。
ax+by=ay1+(x1−⌊ab⌋y1)bax+by=ay_1+(x_1-\left\lfloor\frac{a}{b}\right\rfloor y_1)bax+by=ay1​+(x1​−⌊ba​⌋y1​)b
所以有一组解为x=y1,y=x1−⌊ab⌋y1x=y_1,y=x_1-\left\lfloor\frac{a}{b}\right\rfloor y_1x=y1​,y=x1​−⌊ba​⌋y1​，而这个解显然一定会满足$ax+by=gcd(a,b)$。所以我们不仅证明了它一定有解，还构造出了解的样子和求法。
代码就是这样的：

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

递归边界显然就是当$ax+by=gcd(a,b)$的时候，$b=0$，显然$gcd(a,b)$不合法，所以我们就令$gcd(a,0)=a$，那么原来方程就变为$ax=a$，显然$x=1,y=0$。

辗转相减的用途

既然有更快的辗转相除，那么辗转相减有什么用呢？
我们知道$gcd(a,b)=gcd(a,b-a)$，那么容易推广而知gcd(a1,a2,a3,⋯ ,an)=gcd(a1,a2−a1,a3−a2,⋯ ,an−an−1)gcd(a_1,a_2,a_3,\cdots ,a_n)=gcd(a_1,a_2-a_1,a_3-a_2,\cdots,a_n-a_{n-1})gcd(a1​,a2​,a3​,⋯,an​)=gcd(a1​,a2​−a1​,a3​−a2​,⋯,an​−an−1​)，那么对于一个序列$a$的区间$gcd$，我们可以通过差分的方式快速维护。
题目：bzoj 5028 小Z的加油店

应用

• 求乘法逆元

因为我们可以发现，逆元式子$ax\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{m})$，$x$为逆元，当$gcd(a,m)=1$，它可以写成$a\cdot x=1+b\cdot m$，也就是$a\cdot x+(-b)\cdot m=1$，因为$gcd(a,m)|1$，所以我们用扩展欧几里得算法求出这个方程的一组解，其中的$x$便是它的逆元。友链-逆元求法

• 求方程的一组解（基本操作）

---

• 辗转相除法神奇用法:求以下式子
  ∑i=1n⌊i×pq⌋\sum_{i=1}^{n}\left\lfloor\frac{i\times p}{q}\right\rfloori=1∑n​⌊qi×p​⌋
  具体为转换成三角形求内部整点个数。

• 题目1

• 题目2

推荐这个讲解的友链文章IN

---