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.
利用同餘式的性質:
