频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
数论系列之欧几里得算法和扩展
2016-03-15 09:15:03         来源:北门的智慧  
收藏   我要投稿

欧几里得这部分分为欧几里得算法和扩展欧几里得算法。

 

欧几里得算法即我们经常说的辗转相除法,采用的基本原理是设a-qb+r,其中所有数都是整数,就有gcd(a,b)=gcd(b,r),只用a,b表示的话就是gcd(a,b0=gcd(b,a%b);

代码如下:

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

 

而扩展欧几里得算法则是求 ax+by=c;

其中c%gcd(a,b)==0;不满足就无解

一般的,我们都让这些常量互质,即让a,b,c都除以gcd(a,b);

这时,我们可以得出两个方程:

ax+by=1;

bx1+a%by1=1;

为什么等于1?因为等于1好求,并且最后得出x乘c就好了。

采用第二个式子的原因是,如果一直迭代下去,就会得到一个值,y的系数为1;

此时令当前方程的x=1,y=1-a(当前的a)再递归回去就能解出最开始的x

方法大致是这样的

令 x=y1;

解出当前y与x1之间的关系 然后就一步一步迭代,直到y的系数为1时,再回溯回来就是解了;

当然解不是唯一的 x的解系为x + b/gcd(a,b)*k k为整数。

附代码:

 

void _gcd(long long a,long long b,long long &x,long long &y){
    if(b==1){
        x=1;
        y=1-a;
        return;
    }
    else{
        long long x1,y1;
        _gcd(b,a%b,x1,y1);
        x=y1;
        y=x1-(a/b)*x;
    }
}

 

 

点击复制链接 与好友分享!回本站首页
上一篇:数论系列之一元线性同余方程(组)的解
下一篇:求最小生成树Kruskal算法浅析
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站