中国剩余定理

中国剩余定理

我们先来看这样一个问题:

求满足以下条件的整数:除以3 余2 ,除以 5余3 ,除以 7余2 。

这是中国古代《孙子算经》中的一个问题,并给出了解法, 宋朝数学家秦九韶于 1247 年《数书九章》卷一、二《大衍类》对该问题做出了完整系统的解答。由此诞生了中国剩余定理(CRT),并被国际公认。

那么CRT可用于求解如下形式的一元线性同余方程组。(其中$p_1,p_2,...,p_n$两两互质)

image.png

我们先来看下上面这个问题,求x满足

1.$x;mod;3=2$

2.$x;mod;5=3$

3.$x;mod;7=2$

先看第一个式子,我们假设存在$x_1,x_2,x_3$满足$x_1;mod;3=2,x_2;mod;5=3,x_3;mod;7=2$

那么,我们可以构造$x=(x_1+x_2+x_3)$为原方程组的一个解,我们只需满足一下条件

1.$x_1;mod;3=2$且$x_2,x_3$是3的倍数

2.$x_2;mod;5=3$且$x_1,x_3$是5的倍数

3.$x_3;mod;7=2$且$x_1,x_2$是7的倍数

所以可得,我们要求

1.$x_1;mod;3=2$且$x_1$是(5,7)的公倍数

2.$x_2;mod;5=3$且$x_2$是(3,7)的公倍数

3.$x_3;mod;7=2$且$x_3$是(3,5)的公倍数

那么,运用逆元的思想,我们不妨构造$x_1=2\times 5\times 7\times inv(5\times 7,3)$

这样既保证了$x_1$在是(5,7)的公倍数,同时由于逆元,在mod 3的情况下,$x_1 mod;3$的值也保证为2;

所以我们可以将此推广

由于$p_1,p_2,...,p_n$两两互质,所以LCM($p_1,p_2,...,p_n$)=$p_1p_2...p_n$,记为P

那么$x_i=a_i\times\frac{P}{p_i}\times inv(\frac{P}{p_i},p_i)$

所以得到的 $\sum_{i=1}^{n}x_i$ 即为我们构造出来的一个解。

注意这样构造出来的解并不是最小的,每P个数就会有一个解。所以如果题目要我们求最小的解,我们还要做

$x=(x;mod;p+p)mod;p$

 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
ll exgcd(ll a, ll b, ll &x, ll &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  ll d = exgcd(b, a % b, x, y);
  ll t = x;
  x = y;
  y = t - (a / b) * y;
  return d;
}
ll inv(ll a,ll p)
{   ll x=1,y=0;
    exgcd(a,p,x,y);
    x=(x%p+p)%p;
    return x;
}
ll crt(int n)
{
    ll ans=0,lcmp=1;
    for(int i=1;i<=n;i++) lcmp*=p[i];
    for(int i=1;i<=n;i++)
    {
        ll t=lcmp/p[i];
        ans=(ans+a[i]*t*inv(t,p[i]))%lcmp;
    }
    ans=(ans%lcmp+lcmp)%lcmp;
    return ans;
}

拓展中国剩余定理(exrct)

那么,如果题目中$p_1,p_2,...,p_n$不互质,就不能保证一定存在$inv(\frac{P}{p_i},p_i)$,所以不能再像上面一样构造求解了。

所以就有了拓展中国剩余定理。(其实感觉两者没什么关系,构造的方式几乎完全不一样)

我们先来看只有两个方程的情况。

$x\equiv a_1(mod;m_1)$

$x\equiv a_2(mod;m_2)$

不妨设

$x=x_1m_1+a_1$

$x=x_2m_2+a_2$

所以

$x_1m_1+a_1=x_2m_2+a_2$

由于$x_1;x_2$的取值可以为负无穷到正无穷,所以它们前面的符号即使写反也没关系。

$m_1x_1+m_2x_2=a_2-a_1$

那么这个不定方程可以就可以通过exgcd来求解。

同时,这个求解的过程相当于把这两个方程合并成了一个方程。

$x\equiv c(mod;lcm(m_1,m_2)) $($c$即为这两个方程的最小正整数解)

因此,有多个方程的话,我们只需两两合并下去,就能得到最后的解了。

 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
32
33
34
35
ll m[maxn],a[maxn];
ll exgcd(ll a, ll b, ll &x, ll &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  ll d = exgcd(b, a % b, x, y);
  ll t = x;
  x = y;
  y = t - (a / b) * y;
  return d;
}
ll excrt(int n)
{
   ll M=m[1],A=a[1],x,y,t;
   for(int i=2;i<=n;i++)
   {
      ll d=exgcd(M,m[i],x,y);
      if((a[i]-A)%d) return -1;
      x*=(a[i]-A)/d,t=m[i]/d,x=(x%t+t)%t;//解不定方程
      A=M*x+A,M=M/d*m[i],A%=M;
   }
   A=(A%M+M)%M;
   return A;
}
int main()
{
   int n;
   cin>>n;
   for(int i=1;i<=n;i++) cin>>m[i]>>a[i];
   cout<<excrt(n)<<endl;
   return 0;
}