首页 > 代码库 > 数论 - n元线性同余方程的解法
数论 - n元线性同余方程的解法
note:n元线性同余方程因其编程的特殊性,一般在acm中用的很少,这里只是出于兴趣学了一下
n元线性同余方程的概念:
形如:(a1*x1+a2*x2+....+an*xn)%m=b%m ..................(1)
当然也有很多变形,例如:a1*x1+a2*x2+...+an*xn+m*x(n+1)=b.这两个都是等价的。
判断是否有解:
解线性同余方程,我们首先要来判断方程是否有解,方程有解的充要条件是:d%b==0.其中d=gcd(a1,a2,...an);
解n元线性同余方程,我们是通过将其转化为n元不定方程来解的。
a1*x1+a2*x2+...+an*xn+m*x(n+1)=b ...................(2)
不难证明(2)和(1)是完全等价的,具体证明也很简单,这里就不再证明。
(2)有解的充要条件是:d1%b==0.其中d1=gcd(a1,a2,....an,m).
定理:当(1)有解时,共有d1*m^(n-1)个不同的解。
定理:当(1)
解方程:
设d1=gcd(a1,a2,....an,m),且有d1%b==0.
利用同余式的性质:
数论 - n元线性同余方程的解法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。