CRT学习笔记

一、What is CRT(Chinese Remainder Theory)

中国剩余定理，小学奥数好像就讲过，~~不用学了吧~~

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

—-《孙子算经》

根据这个问题，我们可以很快地写出一个暴力优雅的枚举

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


#include<iostream>
using namespace std;
int main(){
     for(int i=1;;i++){
          if(i%3==2&&i%5==3&&i%7==2){
               cout<<i<<endl;
               break;
          }
     }
     return 0;
}

~~本文完。~~并没有

我们仔细观察一下这个问题，可以简化成一个一元线性同余方程组

$$ \left{ \begin{aligned} &x\equiv a_1\pmod {m_1}\
&x\equiv a_2\pmod{m_2}\
&…… \
&x\equiv a_t\pmod{m_t}\
\end{aligned} \right. $$

且$m_{1}$,$m_{2}$, $\cdots$,$m_{t}$两两互质。

它的解为

$$ 设M = m_{1} \times m_{2} \times m_{3} \times\cdots\times m_{t}= \prod_{i=1}^{t}m_{i} , $$

$$ M_{i}=M/m_{i},\forall i \in \lbrace1,2,…,n\rbrace , $$

$$ t_{i} = M_{i}^{-1},t_{i} 为 M_{i} 模 m_{i}意义下的逆元\
$$

$$ M_{i}t{i}\equiv 1\pmod{m_t},\forall i \in \lbrace1,2,…n\rbrace\
$$

$$ x = a_1t_1M_1+a_2t_2M_2+…+a_nt_nM_n+kM=kM+\sum^n_{i=1}a_it_iM_i,k \in Z\
$$

$$ 在模M的意义下只有一个解 \
$$

$$ x = (\sum_{i=1}^na_it_iM_i)\pmod{M}\
$$

二、CRT的应用

例题 P1495 【模板】中国剩余定理(CRT)/曹冲养猪

就是套公式

$$ 猪的总数\equiv无家可归的猪\pmod{猪圈数} $$

 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


/*
 * @Date: 2021-05-28 19:10:36
 * @LastEditors: stevelbr
 * @LastEditTime: 2021-05-28 20:24:13
 * @FilePath: \c++\P1495.cpp
 */
#include<iostream>
using namespace std;
typedef long long ll;
ll n,a[16],m[16],Mi[16],mul = 1,X;
void exgcd(ll a,ll b,ll &x,ll &y){
    if(b == 0){
        x = 1,y = 0;
        return;
    }
    exgcd(b,a%b,x,y);
    ll z = x;
    x = y,y = z-y*(a/b);
}
int main(){
    cin>>n;
    for(int i = 1 ;i <= n;i++){
        int M;cin>>M,m[i] = M,mul *= M,cin>>a[i];
    }
    for(int i = 1;i<=n;i++){
        Mi[i] = mul /m[i];
        ll x = 0 ,y = 0;
        exgcd(Mi[i],m[i],x,y);
        X += a[i] * Mi[i] * (x<0?x+m[i]:x);
    }
    cout<<X%mul;
}

练习题

1006 – Biorhythms (poj.org)

三、Reference

1.数论选讲（更新中）_zxyoi_dreamer的博客-CSDN博客

2.孙子定理_百度百科

3.~~《孙子算经》~~

4.P1495 【模板】中国剩余定理(CRT)/曹冲养猪