频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
数论系列之一元线性同余方程(组)的解
2016-03-15 09:15:01      个评论    来源:北门的智慧  
收藏   我要投稿

数论,在ACM道路上走的越来越远,提起数论,都是从整除开始,而一元线性同余方程(组)的解,也要从整除起源。

提起整除问题,最负盛名的是欧几里得算法和扩展欧几里得算法,在这里我就不再赘述,而一元线性同余方程(组)的问题的解法源于扩展欧几里得算法。、

对于一元线性同余方程ax≡b(mod c)来说,这个方程等价于ax=by+c,由于y是未知数,所以可以领y=-有,即有ax+by=c。形如上述方程,很显然是扩展欧几里得算法的式子,而满足扩展欧几里得算法的条件是c%gcd(a,b)==0,如果满足这个条件,就可以求解出来x的值。

具体解法如下:

令 g=gcd(a,b);

a=a0×g;

b=b0×g;

所以式子可以改写成为 a0x+b0y=c/g;此时gcd(a,b)=1,运用扩展欧几里得算法可以解出一个x,但x不唯一,x是一个模b的系,所以x的取为

x,x+b0,x+2b0,……x+(g-1)b0。

对于一元线性方程组而言,这个问题就复杂了一些。一元线性方程组是形如

m≡a0(mod b)
m≡a1(mod b)
m≡a2(mod b)
m≡a3(mod b)
?

的式子求x的解。不难发现,我们拿出两个式子来 :
m≡a0(mod b0)
m≡a1(mod b1)

不难看出此时式子可以改写为:

m=a0x+b0

m=a1y+b1

所以可以得到一个式子就是 a0x+a1y=b1-b0,这样就成为了扩展欧几里得算法的式子,再用这个x求出m。

这时我们引入第三个式子 m≡a2(mod b2),此时m=a2y+b2;由于引入了新的式子,所以此时m的值也法生变化,姑且将上一个解出的m称之为m0。

因为x的解是一个系,所以有a0(x+a1/gcd(a0,a1)*k)+b0;所以有a0x+(0a1/gcd(a0,a1))k+b0=m。m0=a0x+b0,所以得出一个新的递推式即(a1a2/gcd(a1,a2))k+a2y=b2-m0;
由此可以一步一步求解出x的值

附代码:

 

long long a1,b1,a2,b2;
        int flag=1;//判断是否有解
        
        //a1,b1的值在循环外赋值
        for(int i=1;i0;
            x=x*a1+b1;
            b1=x;
            a1=b*a1;
        }
        //最后b1是最终解



 

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 数论 线性 方程
上一篇:关于getchar函数缓冲区的问题分析
下一篇:数论系列之欧几里得算法和扩展
相关文章
图文推荐
点击排行

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

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