P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪 讲解

· · 题解

首先它是用来求以下方程组的解的：

\begin{cases}x\equiv a_1\pmod{m_1}\\x\equiv a_2\pmod{m_2}\\\vdots\qquad\vdots\hspace{1cm}\vdots\\x\equiv a_n\pmod{m_n}\end{cases}

注：对于任意的 i,j(1\le i,j\le n,i\ne j)，\gcd(m_i,m_j)=1。
那么怎么解呢？
我们定义 m=\prod_{i=1}^nm_i，M_i=\frac{m}{m_i}，M_iN_i\equiv1\pmod{m_i}(1\le i\le n)。
那么最后解的形式就是：

x\equiv\sum_{i=1}^na_iM_iN_i\pmod m

答案可不可行呢？我们就拿 x\equiv a_1\pmod{m_1} 举例：

\begin{aligned}x\bmod m_1&=(\sum_{i=1}^na_iM_iN_i)\bmod m_1\\&=\sum_{i=1}^na_iM_iN_i\bmod m_1\\&=a_1M_1N_1\bmod m_1(\text{对于 }1\le i\le n,i\ne 1,m_1|M_i)\\&=a_1\times1(M_1N_1\bmod m_1=1)\\&=a_1\end{aligned}

其余同理。（啥？你说你不会扩欧？）

扩欧适用于解决类似以下方程的：

ax+by=\gcd(a,b)=c

怎么解决呢？
考虑以下式子是否成立：

ax+by=bx+(a\bmod b)y

它是成立的，因为 ax+by=\gcd(a,b)，bx+(a\bmod b)y=\gcd(b,a\bmod b)，而 \gcd(a,b)=\gcd(b,a\bmod b)。
然后我们一直向下，直到 a=1,b=0，这时：

1\times x+0\times y=c

解得 x=c,y=114514。
那么，我们能否用这一次的解推出上一次的解呢？
我们对其进行拆分：

\begin{aligned}b_0x+(a_0\bmod b_0)y&=b_0x+(a_0-\lfloor\frac{a_0}{b_0}\rfloor\times b_0)y\\&=b_0x-\lfloor\frac{a_0}{b_0}\rfloor\times b_0\times y+a_0y\\&=a_0y+b_0(x-\lfloor\frac{a_0}{b_0}\rfloor\times y)\end{aligned}

与 a_1x+b_1y 放在一起，我们发现 x=y，y=x-\lfloor\frac{a_0}{b_0}\rfloor\times y。
根据以上内容，易得代码： 

#include<bits/stdc++.h>
#define int long long
#define inl inline
#define INF 214748364721474836
#define rep(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
inl int read(){
    int f=1,x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return f*x;
}
inl void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>=10) write(x/10);
    putchar(x%10^48);
    return;
}
int n,a[15],m[15],num=1,M[15],N[15],ans1,ans2,sum;
inl void exgcd(int a,int b){
    if(!b){
        ans1=1;
        ans2=0;
        return;
    }
    exgcd(b,a%b);
    int copyans=ans1;
    ans1=ans2;
    ans2=copyans-a/b*ans2;
}
signed main(){
    n=read();
    rep(i,1,n){
        m[i]=read();
        num*=m[i];
        a[i]=read();
    }
    rep(i,1,n) M[i]=num/m[i];
    rep(i,1,n){
        exgcd(M[i],m[i]);
        N[i]=ans1;
    }
    rep(i,1,n) sum+=M[i]*N[i]*a[i];
    write((sum%num+num)%num);
    return 0;
}