转载请注明博客原址：http://blog.csdn.net/sunliymonkey/article/details/48102067

1 算法实现

1.1 欧几里德算法(辗转相除法)

欧几里德算法，也被称为辗转相除法，其被用于求解两个数之间的最大公约数，常用$gcd(A，B)$进行表示。

它的算法实现十分容易，如下：

int gcd(int a,int b)
{
    if(b==0)
      return a;
    else 
      return gcd(b,a%b);
}

1.2 扩展欧几里德算法

扩展欧几里德算法是用来求解这样一个式子：

　　　　　　　　$A * x + B * y = gcd(A，B)$
　　　　　　　　求解： $x= ?$ , $y= ?$
这里的x，y不是唯一解，当得知一组可行解之后，其它的可行解都可以表示出来：
　　　　　　　
　　　　　　　　$x^k = x + \left( k*\frac{B}{gcd(A, B)} \right)$
　　　　　　　　$y^k = y - \left( k*\frac{A}{gcd(A, B)} \right)$
　　　　　　　　$k$ 为任意整数　　　　　　　　　　　　　

在这里不阐述，x，y的值有何用处，如果你是acmer，应该发现有不少题，需要利用这个性质。

扩展欧几里德算法的实现也很简单，在原有欧几里德算法的基础上，少许额外的代码，即能实现：

    int exGcd(int a,int b,int &x,int &y)  
    {  
        if(b==0)  
        {  
            x = 1;  
            y = 0;  
            return a;
            // 此时a = gcd(A,B)  
            // a * 1 + b * 0 = gcd(A,B)
            // 由于b=0，y可以任意取值
        }  

        int d = exGcd(b, a%b, y, x); // 注意这里x，y的位置对调  
        y -= a/b * x;  
        return d; // 返回最大公约数  
    }  

2 状态转移思想

看了上面的实现，相信你的第一感觉是十分简洁，确实也如此，对于一个不懂这两种算法的人，如果提醒你从“动态规划”,“状态转移”等角度思考这两个问题，相信会有不少人能够AC它们。

先来看看两个明显的结论：

• $如果A=B， gcd(A,B)=A或B$

• $如果A=0， gcd(A,B)=B，同理，如果B=0，gcd(A，B)=A$

看到这里，相信你会有一种直觉：是否能够将求解$gcd(A,B)$, 转换成更小的两个数$A_1,B_1$，使得$gcd(A,B)=gcd(A_1,B_1)$呢？而这种状态转移思想经常被用到：

• 分治： 大问题分解成小问题，小问题更容易被解决，最终，合并小问题的结果，解决大问题

• 动态规划： 一个状态能够从多个状态转移而来，其最优值将从这多个状态的最优值中选取

3 状态转移方程

3.1 欧几里德

结论：　$gcd(A,B)=gcd(A-B,B)$

证明：

　设 $A=k_1*gcd(A,B), B=k_2*gcd(A,B) (A \geq B)$

　显然 $gcd(k_1,k_2) = 1$

　$A-B=(k_1-k_2)*gcd(A,B)$

　可以使用反证法证明： $gcd(k_1-k_2，k_2)=1$
　因此$gcd(A,B)=gcd(A-B,B)$

　当你发现存在这样的状态转移，欧几里得算法，其实已经解决了。然后再分析下，不难发现更快速的状态转移方程：

　　　　　$gcd(A,B)=gcd(A\%B,B)$

　而这就是上面代码实现中，使用的状态转移方程。

3.2 扩展欧几里德

有了上面状态转移的基础，我们可以将问题进行如下转换：
状态转移：$(A_0,B_0,x_0,y_0) \leftarrow (A_1, B_1,x_1,y_1)$

　　　　　$A_0*x_0+B_0*y_0=gcd(A,B)$
　　　　　$A_1*x_1+B_1*y_1=gcd(A,B)$

其中：
　$A_1 = B_0$
　$B_1 = A_0\%B_0 = A_0 - (A_0/B_0)*B_0$
　$x_1,\ y_1$的值已经知道，现在需要反推出$x_0,\ y_0$的值

只需代入上面的关系，即可推导出状态转移的公式：

　 $A_1*x_1+B_1*y_1$

　$=B_0*x_1+[A_0 - (A_0/B_0)*B_0]*y_1$

　$=A_0*y_1+B_0*[x_1- (A_0/B_0)*y_1]$

　$=A_0*x_0+B_0*y_0$

推导结果：

　$x_0=y1$
　$y_0=x_1- (A_0/B_0)*y_1$

扩展欧几里德算法，就这样被你解决了！