【数学】【exgcd】exgcd详解（含证明）

Singercoder · 2020-05-07 13:30:16 · 个人记录

序

5.7，得知即将开学的好消息，心情复杂。

想想鸽了半年的exgcd，更思绪万千。

前置概念

• gcd：即最大公约数。

• lcm：即最小公倍数。有结论lcm(a,b)=a * b/gcd(a,b)，可以简单理解为a、b相乘后除去重复的公因数。

• 欧几里得算法：又称辗转相除法。核心结论gcd(a,b)=gcd(b,a\%b)，作为经典算法网上证明还是很多的，不加赘述。

• 裴蜀定理：不定方程ax+by=c有解的充要条件为gcd(a,b)|c，网上证明也很多。

  常见的一种应用为，不定方程ax+by=1有解的充要条件为a,b互质。

  这个定理对于下文求解不定方程很重要，简单证明一下必要性：设g=gcd(a,b),a=pg,b=qg，则p,q互质。那么为a,b添加系数x,y后，可得c=ax+by=(px+qy)g，故g|c。但充分性的证明可能更加复杂，可以自己搜集资料。这里的必要性证明仅为方便理解。

  另附某dalao的裴蜀定理扩展证明证明，就是将常数a,b的个数从2个扩展到n个，依旧满足gcd|sum的关系。

扩展欧几里得算法

• 如果说裴蜀定理描述了不定方程的特征，那么扩展欧几里得算法就是给出了一种求解不定方程的有效算法。

• 算法思路：利用欧几里得算法求出gcd(a,b)，即得到不定方程ax+by=gcd(a,b)，在令a=gcd(a,b),b=0的情况下所得到的一组特殊解x=1,y=0，然后通过这个特殊解，步步回溯欧几里得算法的过程并修改x,y的值，以得到初始状态下的x,y。

  这个回溯过程仅由一组简单的式子组成，其描述了欧几里得算法上下步状态间的内在关系。并不建议背诵，而是理解证明这个式子的过程，这也是这篇文章的核心所在。

• 回溯过程证明：

  设这一步和下一步的式子分别为：

  ax_1+by_1=gcd(a,b)\\ bx_2+cy_2=gcd(b,c)\\ \end{cases}

  其中c=a\%b=a-a/b * b。

  由欧几里得算法的定理可得gcd(a,b)=gcd(b,c)，

  则有ax_1+by_1=bx_2+cy_2。

  即ax_1+by_1=bx_2+(a-(a/b * b))y_2。

• 证明到此暂停一下，我们需要时刻明确已知和所求。由上文算法思路可知，由求解gcd(a,b)，我们可以得到a=gcd(a,b),b=0时x=1,y=0的一组解。也就是说，我们的已知量是下一步式子的x_2,y_2，和这一步式子的a,b(每一步的a,b本来就已知)，而要求的是这一步的x_1,y_1。

• 思路很明确了，直接变形，得到：

  ax_1+by_1=ay_2+b(x_2-a/b * y_2)

  由此得到x_1,y_1的值：

  x_1=y_2\\ y_1=x_2-a/b * y_2 \end{cases}

  如此得到的x_1,y_1能满足这一步的方程依旧成立，顺利完成回溯。反复回溯得到初始状态的解即可。

• 得到ax+by=gcd(a,b)的解了，再成倍变化x,y即可得到ax+by=c的解。

模板分析p1082

可见题目已知a,b互质，要求的是ax+by=1的x的最小正整数解。

先尝试利用exgcd求得一组解，不难想象若x-=b,y+=a，则方程依旧成立，由此可求得x的最小正整数解。

实际上普遍地，对于\forall x,y \in N_+,g=gcd(a,b),x=pg,y=qg，则不定方程ax+by=c的一组解x,y，在x-=q,y+=p后仍成立。

#include<cstdio>
using namespace std;
int exgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x=1;y=0;
        return a;
    }
    else//实际程序中为简化代码，常常将x,y的位置调换后再向下计算，方便回溯 
    {
        int g=exgcd(b,a%b,y,x);
        y-=a/b*x;
        return g;
    }
}
int main()
{
    int a,b,x,y,g;
    scanf("%d %d",&a,&b);
    g=exgcd(a,b,x,y);
    x=(x%b+b)%b;
    printf("%d\n",x);
    return 0;
}

后记

• 复杂度分析：同欧几里得算法，在最坏情况下所有a,b呈斐波那契数列排布，复杂度logn，效率还是很优秀的。

• 应用：除了常见的duliu数论题，求某个数的逆元也要用到exgcd（留坑）。