本文写于2017-11-02，其中的一些思路可能存在问题，公式也未用LATEX编写。本文移至此处时暂未重新学习。

    先学习一下最大公约数的求法：

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

    扩展欧几里得的代码：

    1. void exgcd(int a,int b,int &x,int &y)
    2. {
    3.     if(b==0) x=1,y=0;
    4.     else
    5.     {
    6.        exgcd(b,a%b,y,x);
    7.        y-=a/b*x;
    8.     } 
    9. }

    调用的时候，用exgcd(a,b,x,y)，x,y就成为了ax+by=1的一组解。如果是ax+by=c，那直接给x,y乘c即可。x=x-b,y=y+a也是一组解。

    gcd(x,y)lcm(x,y)=xy