算法基础-中国剩余定理

原题链接

题目大意描述

给定 2n个整数 a1,a2,…,an 和 m1,m2,…,mn，求一个最小的非负整数 x，满足 ∀i∈[1,n],x≡mi(mod ai)。

题目拆解

同余不好做运算，转换为等式运算。

判断是否有解

x≡m1(mod a1)  ==> x=a1*k1+m1 ①

x≡m2(mod a2)  ==> x=a2*k2+m2 ② 

a1*k1+m1 = a2*k2+m2; ==> a1*k1-a2*k2 = m2-m1; ③

  ③式左边可以用扩展欧几里得算法求a1*k1-a2*k2的值d
  ③式有解的充要条件是m2-m1是d的整数倍,记作 d|(m2-m1)
  所以判断是否有解即判断 (m2-m1)%d 是否为0,0有解非0无解
  
 
1
2
3
4
5
6
7
8
9
10
11

求k1

因为x=a1*k1+m1,a1和m1已知，k1得解后，x既可以算出。

重要性质

对于③式
除了k1 k2可以满足
k1 + k * a2/d 和 k2 + k * a1/d同样可以满足 ,证明略过

1
2
3
4

推论

k1 + k * a2/d 同样是一组解
带入①
x = a1*(k1+k*a2/d)+m1 
x= a1*a2/d * k + a1*k1+m1 ==>  a0* k+ m0 (a0=a1*a2/d,m0 = a1*k1+m1) ④
④式和①、② 相同形式

推论 
利用①、② 可以推出 ④式，④式又可以和接下来⑦合并，以此下去，最终可以算出符合这个n个同余式的解
求出最终的k1的值，带回①式即可求出x
x≡m3(mod a3)  ==> x=a3*k3+m3 ⑦
1
2
3
4
5
6
7
8
9
10

注意点

k1需要取余

要求x的最小值，因为x=a1*k1+m1，那么k1在计算过程中需要最小

因为k1 + k * a2/d
所以计算过程中需要取余既可以保证k1的值最小
k1 = k1 % (a2/d)
1
2
3

负余数转换为正余数

计算机的取余计算是使得商尽量靠近0，传统数学上取余余数都是大于0

例如 -5 % 3

计算机：-5 % 3 = 1（商）-2（余数）

传统数学：-5 % 3 = 2（商） 1（余数）

假设Y%T是负数,取余保证余数是正数的话可以这么写
(Y%T+T)%T
1
2

扩展欧几里得算法

线性方式里都会用到，需要熟练掌握

关键代码

扩展欧几里得算法

注意类型，10^9需要用 long long 类型

LL exgcd(LL a,LL b,LL &x,LL &y){
  if(!b){
    x=1,y=0;
    return a;
  }
  
  LL d = exgcd(b,a%b,y,x);
  y -= a/b*x;
  return d;
}
1
2
3
4
5
6
7
8
9
10

中国剩余定理

LL a1,m1;
cin >> a1>>m1;
bool has_answer = true;
for(int i=0,i> a2>> m2;
  LL k1,k2;
  LL d = exgcd(a1,a2,k1,k2);
  
  //判断是否有解
  if((m2-m1) %d){
    has_answer =false;
    break;
  }
  
  //此时k1是公式=d的解，公式=m2-m1的解需要把k1扩大(m2-m1)/d倍
  k1* = (m2-m1)/d;
  //保证k1最小，取余
  LL t = a2/d;
  //保证余数为正数
  k1 = (k1%t+t)%t;
  
  //下一轮合并用到的m1
  m1= a1 *k1+m1;
   //下一轮合并用到的a1
  a1 = abs(a1/d*a2); 
  
}

if(has_answer) cout<< (m1%a1+a1)%a1;
 else cout << "-1"<< endl;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31