裴蜀定理与扩展欧几里得算法

裴蜀定理： 对于一对正整数a,b,由余数的性质，显然

\forall x,y \in Z,有 gcd(a,b) \mid ax+by\\
即a,b的线性组合总被最大公约数d整除

而特别的

\exists  x,y \in Z,令 gcd(a,b) = ax+by

例如

a=15,b=25\\d=gcd(a,b)=5\\而d = 2a-b

扩展欧几里得算法便是求得在②式中x,y的值的有效方法

复习一下欧几里得算法（辗转相除法）

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

这里给出一个推导过程

令d=gcd(a,b)=gcd(b,a\%b) \\
ax+by=d\\
bx_1+(a\%b)y_1=d\\
联立有ax+by=bx_1+(a\%b)y_1\\
又a\%b=a-[\frac{a}{b}]b\\
整理系数可得\\
\begin{cases}
  & x=y_1 \\
  & y=x_1-[\frac{b}{a}]y_1\\
\end{cases}\\

观察结论，不难发现x1，y1的规模要比xy本身要小，所以可以递归解决该问题

同样的，在递归出口b==0时，返回gcd=a，对于该局部问题，有x=1,y=0 因为gcd=a=1a+0b

综上可以写出扩展欧几里得算法的完整代码

//xy的值以引用的方法传回
int exgcd(int a, int b, int &x, int &y)
{
    if(!b)
    {
        x = 1; y = 0;
        return a;
    }
    int res = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return res;
}