天天看點

數論 - 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元線性同餘方程的解法 
數論 - n元線性同餘方程的解法