你说得对，但 CRT 全称叫中国单身狗定理！

DX3906_ourstar · 2025-03-06 12:55:35 · 题解

看到题面第一反应：小学奥数？

其实咱小时候都是巨佬，比如一笔画问题，它的大名叫欧拉路径。

废话结束，正片开始。

本篇题解主要参考自 寒假集训时的课件。

中国剩余定理，主要用于求解线性同余方程组，也就是形似这样的一堆式子。

在接下来的讲解中，我们记 r 为余数集合，m 为余数集合，n 为方程数量。

那么，依据中国剩余定理，我们就可以这样解上面的方程组：

1. 求 \prod\limits^n_{i=1}，并将其记为 M；

2. 定义一个新集合 c，其通项式为 c_i=\frac{M}{m_i}；

3. 对于 \forall i \in [1,n]，计算 c_i 在模 m_i 意义下的逆元，并写入新集合 d；

再回来看本题。为什么想到 CRT？因为标题 因为题意可以直接转化为：给定由 n 个形似 x \equiv b \mod a 的线性同余方程构成的方程组，求 x 的最小值。

至此，我们就可以写出一份 AC 代码了。

#include<iostream>
#define ll __int128
using namespace std;

const int N=1e1+5;

int n;
ll ans;

namespace OIfast{

    inline ll read(){
        register ll n=0,f=1;
        register char c=getchar();
        while(c<'0'||c>'9'){
            if(c=='-')f=-1;
            c=getchar();
        }
        while(c>='0'&&c<='9'){
            n=(n<<1)+(n<<3)+(c^48);
            c=getchar();
        }
        return n*f;
    }

    inline void print(register ll n){
        if(n<0)n=~n+1,putchar('-');
        if(n>=10)print(n/10);
        putchar(n%10^48);
        return ;
    }

    inline void write(register ll n,register char c){
        print(n),putchar(c);
        return ;
    }

}using namespace OIfast;

namespace numberTheoryTools{

    ll m=1;
    ll x,y;
    ll a[N]/*模数*/,b[N];

    inline void exgcd(ll a,ll b){
        if(b==0){
            x=1,y=0;
            return ;
        }
        exgcd(b,a%b);
        ll tmp=x;
        x=y;
        y=tmp-a/b*y;
//      cout<<"x:"<<x<<",y:"<<y<<"\n";
        return ;
    }

}using namespace numberTheoryTools;

signed main(){
//  freopen("P1495_3.in","r",stdin);
    n=read();
    for(int i=1;i<=n;++i){
        a[i]=read();
        b[i]=read();
        m*=a[i];
    }
    for(int i=1;i<=n;++i){
        ll c=m/a[i];
        exgcd(c,a[i]);
        ans=((ans+b[i]*c*x)%m+m)%m;
    }
    write(ans,'\n');
    return 0;
}

当时写的时候没用上面提到的变量名，懒得改了。

那么这时候就有同学会问了：这样做的依据是什么？

那么，接下来，我们就一起证明一下 CRT。

宣一下大佬 XXh 的 证明。

先看到我们最终得出答案的式子：

容易发现，对于 \forall i \in [1,n]，都有 x\equiv r_i \pmod {m_i}。

接下来再随便找一个 j，分情况讨论。

首先，考虑 i \neq j。此时 c_j \equiv 0 \pmod{m_i}，那么容易发现，c_jd_j \equiv 0 \pmod{m_i}。

然后，考虑 i = j。易证 c_j \not\equiv 0 \pmod{m_i}，则显然有 c_jd_j \equiv 1 \pmod{m_i}。

于是，分讨完毕，我们来整合一下。下面的计算都在模 m_i 意义下进行。