线性同余系列

线形同余方程系列

求解形如 : ax ≡ b (mod n)

方程可以变形为 : ax – ny = b; 对于这个方程的求解可以使用扩展欧几里得定理做，有解的首要条件便是gcd(a ,n) 能够整除b ; 证明如下：如果(a ,n) 不能够整除b ,那么方程两边同除以(a ,n)，有 a’x – n’y = b/(a ,n) ; 可以看出，方程左边肯定是整数，右边却为小数，所以(a ,n) 肯定能够整除b ;

对于方程： ax – ny = gcd(a ,n);通过扩展欧几里得可以求出方程的某个解: 假设求得x0，那么方程其余解可以表示为 : x0 + k* n/(a ,n); k∈Z(对于这个通解，我参考很多网上的资料，可是说得都不是很清楚，智商不高的我表示我研究两天才有所领悟) ; 首先，由于y=ax/n; (这里的除法是计算机语言中的除法) 也就是说随着 x 的变化，y是可以相应变化。。那么，x0满足条件 ,x1=x0+n也满足条件，对应y1=y0+a; 但我们可以缩小这个间距，那么是不是y1=y0+1;满足条件呢？此时的x1=x0+n/a; 但由于求的是整数解，我们无法保证n/a 是一个整数。那么也就是说我们要找的就是t ∈ [1,n]，使得n/t是个整数且t最大，当然同时还要满足a*n/t % n==0;

那么就有a/t *n % n ==0; 也就是 a / t 也得是一个整数，那么能够被a、n整除的最大t便是 gcd(a ,n);所以通解为 xk= x0 + k*n/(a ,n); k∈Z; (为啥总觉得自己把一个很简单的问题想得太复杂呢。。。因为通过这个式子：，可以很容易看出通解的间距为： n’; 66666... )

　现在来看线性同余方程组:

解决形如: x ≡ b1 (mod a1); ①

　 x ≡ b2 (mod a2); ②

x ≡ bi (mod ai);

解决方法是两两一对求解，然后再通过得到的解构造一个新的方程，然后递推求解。

首先：由 ①、② 得 a1 * k1 – a2 * k2 = b2 - b1; ③

那么方程组有解的首要条件便是 gcd(a1,a2) | (b2-b1);如果不满足这个条件，方程无解。

式子 a1 * k1 – a2 * k2 = gcd(a1,a2);通过扩展欧几里得定理可以求出某个解k1, 那么式子 ③ 中的k1=k1*(b2-b1)/(a1,a2);

　由于要让k1 尽量小，且为正整数 ; 令 t= a2/(a1,a2); 那么有k1=(k1 % t + t ) % t; (t 的由来参看上部分)

现在可以明了方程组的解为 x = a1 * k1 + b1; ④

那么可以构造出第三个式子 : b1 = x; a1= lcm[a1,a2];

关于构造第三个式子的理解：如果只有两个方程式子，那么现在得出的解x便是满足条件的最小解x，但如果还有第三或者更多的线性同余方程，那么如果最后的解x’大于x，那么他必然满足 x’% lcm[a1,a2] == x; 即 x’就是 ④ 的通解。

如果说上面的理解还有需要想象的地方(0.0 我反正找不到...)，那么下面我给出比较严谨的公式推导过程：

x ≡ b1 (mod a1); ①

　x ≡ b2 (mod a2); ②

由 ① 得 x = a1*k1+b1; ③

将 ③ 代入 ② ：有 a1*k1+b1 ≡ b2 (mod a2) ;

　--> a1*k1 ≡ b2-b1 (mod a2); ④

　令 d= gcd(a1,a2); B= b2-b1;

　由 ④ 有： a1*k1 = k2*a2+B;

　--> a1*k1/d = k2*a2/d + B/d ;

　令B’= B/d;

　有 a1*k1/d = k2*a2/d + B’; ⑤

　由 ⑤ 得： a1*k1/d ≡ B’(mod a2/d);

　--> k1 ≡ K (mod a2/d);

　--> k1 = k’*a2/d + K; ⑥　

　将 ⑥ 代入 ③ :

　x = (k’*a2/d + K)*a1+b1;

　--> x = k’*a1*a2/d +K*a1 +b1;

　--> x ≡ K*a1 +b1 (mod a1*a2/d); ⑦

　由 ⑦ 也验证了构造出来的新方程的a’= a1 * a2 / d ; b’= K * a1 + b1 ;

上面讨论的是方程组x前面没有系数的情况，但如果前面存在系数w1，做法也几乎一样，就是先两边同除以gcd(wi,ai);得到式子：wi’* x ≡ bi’(mod ai’)，然后此时可求wi'关于ai'的逆元e，最后化得x≡bi'*e (mod ai')的形式，比如3x ≡ 2 (mod 5) ; 3、5 的公约数是1 ，所以第一步已经完成，现在3、5的逆元为2（即满足3*2 ≡ 1 (mod 5) ）所以式子变成 x ≡ 4 (mod 5);

以上的解法是通用于这类型题的，如果题目中多一个限制条件:强调a1、a2、…、ak是互质的，那么可以用中国剩余定理来解，解法如下：

从刚才通用的解法中，我们也可以看出最后的解范围为0<=x<=lcm[a1,a2,…,ak]，如果a1、a2等是互质的话，设他们的最小公倍数为M，M=a1*a2*…*ak;记Mi=M/ai;那么必然存在整数解p,q使得Mi*pi+ai*qi=1;(因为gcd(Mi,ai)==1,这个就不用我解释吧)，记ei=Mi*pi;那么有：

ei ≡ 0 (mod aj) ; j!=i; 这个比较好理解吧,Mj中包括着ai;

ei ≡ 1 (mod aj) ; j==i; Mj中不包括ai;

所以可以很容易得出，线性同余方程组的通解为 x = e1*b1+e2*b2+ ...+ek*bk ; 这个就是单纯地从定义得到，比如：e1 % a1 = 1 ; 那么 e1 * b1 % a1 =b1; 而其他项取余 a1 都等于0，所以得出的这个式子肯定满足上面那k个线性同余方程，当然，如果想要最小正整数解，可以通过加减M来得到。这个适用于a1、a2、…、ak互质的情况。

……以上就是解决线性同余方程组的方法了。

给一道模板题： http://acm.fzu.edu.cn/problem.php?pid=1402

 1 #include<stdio.h>
 2 typedef long long LL;
 3 void exGcd(LL a,LL b,LL &d,LL &x,LL &y)
 4 {
 5   if(b==0)
 6   {
 7     d=a;
 8     x=1;
 9     y=0;
10   }
11   else
12   {
13     exGcd(b,a%b,d,x,y);
14     int t=x;
15     x=y;
16     y=t-a/b*y;
17   }
18 }
19 int main()
20 {
21   LL n,a1,a2,b1,b2;
22   LL x,y,d,ans;
23   while(scanf("%I64d",&n)!=EOF)
24   {
25     ans=1;
26     scanf("%I64d%I64d",&a1,&b1);
27     for(LL i=1;i<n;i++)
28     {
29       scanf("%I64d%I64d",&a2,&b2);
30       exGcd(a1,a2,d,x,y);
31       if((b2-b1)%d!=0)
32       {
33         ans=0;
34       }
35       LL t=a2/d;
36       x=(x*(b2-b1)/d%t+t)%t;
37       b1=a1*x+b1;
38       a1=a1*a2/d;
39     }
40     if(ans!=0)
41       printf("%I64d
",b1);
42   }
43   return 0;
44 }