yuanyuelang

常用链接

统计

最新评论

数论(2)-------扩展欧几里得算法

扩展欧几里得算法------求解线性方程ax+by=c

1.应用：
      线性方程ax+by=c ,已知a,b,c，求解x,y.

2.基本思路：
    
      ax+by=c有解 => c=k*gcd(a,b)=kd（因为d=gcd(a,b)=>d|(ax+by))
      
      我们先考虑求解  ax+by=d
        由欧几里得算法,d=bx'+(a mod b)y'=bx'+(a-[a/b]b)y'=ay'+b(x'-[a/b])y'    
        则由上述两式子，我们可以得出 x=y' ,y=x'-[a/b]y'
        这样子，在欧几里得算法添加x,y变量，最后得到解。（可结合下面代码源代码进行理解）

      接下来我们来看看ax'+by'=d和ax+by=c之间的关系
      
        （c/d)ax'+(c/d)by'=(c/d)d 即 可以得到 x=(c/d)x',y=(c/d)y'
         
         所以可以得到ax+by的一组解
         那么ax+by=c所有解的形式是什么呢？
             a(x+qb)+b(y-qa)=c; q为任意整数
(注意，当要求y-qa的最小正整数min时,由y-qa>=0， q取[y/a]最小，min=y-[y/a]y,但是,[y/a]可能为0，如果y是负数，min此时也为负数，不好，此时令min+=a就可以取得最小正整数值了（[y/a]=0所以|y|<a),这段可以自己找个例子好好理解下啊）

3.源代码模板
 1int Extended_Euclid(int a,int b,int& x,int &y)
 2{
 3    if(b==0){
 4        x=1;
 5        y=0;
 6        return a;
 7    }
 8    int d=Extended_Euclid(b,a%b,x,y);
 9    int temp=x;x=y;y=temp-a/b*y;
10    return d;
11}
12//用扩展欧几里得算法解线性方程ax+by=c;
13bool linearEquation(int a,int b,int c,int& x,int &y)
14{
15    int d=Extended_Euclid(a,b,x,y);
16    if(c%d) return false;
17
18    int k=c/d;
19    x*=k;y*=k;//求的只是其中一个解
20    return true;
21}

四.学习心得
    扩展欧几里得算法的妙用，值得好好体会，对整个过程自己可以找个例子好好印证一下，肯定印象深刻。去Google一下POJ上的这方面的题目好好实践一下吧！！！

posted on 2009-09-05 16:51 原语饿狼 阅读(4209) 评论(4)  编辑 收藏 引用 所属分类: 数论

评论

# re: 数论(2)-------扩展欧几里得算法 2011-02-02 09:34 ding

顶  回复  更多评论   

# re: 数论(2)-------扩展欧几里得算法 2011-04-07 23:08 晓楠

由欧几里得算法,d=bx'+(a mod b)y'=bx'+(a-[a/b]b)y'=ay'+b(x'-[a/b])y'

这句话应该是
d=bx'+(a mod b)y'=bx'+(a-[a/b]b)y'=ay'+b(x'-[a/b]y')
  回复  更多评论   

# re: 数论(2)-------扩展欧几里得算法 2011-10-03 17:34 CrazyForAC

min=y-[y/a]y错了.  回复  更多评论   

# re: 数论(2)-------扩展欧几里得算法 2013-12-15 20:43 s

定理：gcd(a,b) = gcd(b,a mod b) (a>b 且a mod b 不为0)  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理