中国剩余定理

2021-01-22

数论题解

封面来源

Pixiv 夕燒-95681740

CRT学习笔记

一、What is CRT(Chinese Remainder Theory)

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

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

—-《孙子算经》

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

cpp

#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;
}

~~本文完。~~并没有

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

且,, ,两两互质。

它的解为

二、CRT的应用

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

就是套公式

cpp

/*
 * @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;
}