扩展欧几里得算法算法摘记

现在的位置: 首页 > 综合 > 正文

RSS

扩展欧几里得算法算法摘记

2017年11月22日 ⁄ 综合 ⁄ 共 1061字 ⁄ 字号小中大 ⁄ 评论关闭

扩展欧几里得算法是欧几里得算法（又叫辗转相除法）的扩展。已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足贝祖等式 $ax + by = \gcd(a, b).$ 。

用类似辗转相除法，求二元一次不定方程47x+30y=1的整数解。

47=30*1+17
30=17*1+13
17=13*1+4
13=4*3+1

然后把它们改写成“余数等于”的形式

17=47*1+30*(-1) //式1
13=30*1+17*(-1) //式2
4=17*1+13*(-1) //式3
1=13*1+4*(-3)

然后把它们“倒回去”

1=13*1+4*(-3) //应用式3
1=13*1+[17*1+13*(-1)]*(-3)
1=13*4+17*(-3) //应用式2
1=[30*1+17*(-1)]*4+17*(-3)
1=30*4+17*(-7) //应用式1
1=30*4+[47*1+30*(-1)]*(-7)
1=30*11+47*(-7)

得解x=-7, y=11。

基本算法：对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。
证明：设 a>b。
　　1，显然当 b=0，gcd（a，b）=a。此时 x=1，y=0；
　　2，ab!=0 时
　　设 ax1+by1=gcd(a,b);同理：
　　 bx2+(a mod b)y2=gcd(b,a mod b);
　　根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);
　　则:ax1+by1=bx2+(a mod b)y2;
　　即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;
　　根据恒等定理得：x1=y2; y1=x2-(a/b)*y2;
这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.
　上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以结束。

int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    int r=exgcd(b,a%b,x,y);
    int t=x;
    x=y;<span style="font-family: sans-serif;">//x1=y2</span>
    y=t-a/b*y;//y1=x2-(a/b)*y2
    return r;
}

http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html