中国剩余定理(学习笔记)

PPXppx · 2019-03-09 15:56:41 · 个人记录

定义:若m_1,m_2 \cdotsm_n是两两互质的正整数，M= \prod_{i=1}^n{m_i}，M_i=M/m_i,t_i是线性同余方程M_it_i≡1（mod m_i）的一个解.对于任意的n个整数a_1，a_2 \cdots a_n，则同余方程组：

有整数解，方程组的解为x=a_1M_1t_1+a_2M_2t_2+ \cdots +a_nM_nt_n.并且在\mod M意义下有唯一解.

证明：因为M_i=M/m_i是除m_i之外所有模数的倍数，所以\forallk\not=i，a_iM_it_i≡0(mod m_k).又因为a_iM_it_i≡a_i(mod m_i)，所以代入x=\sum_{i=1}^{n}{a_iM_it_i},成立.

结论:中国剩余定理给出了模数两两互质的线性同余方程组的一个特殊解.方程组的通解可以表示为x+kM(k∈Z).有些题目要求我们求出最小的非负整数解，只需把x对M取模，并让x落在0~M-1的范围内即可.

因为条件中有t_i是线性同余方程M_it_i≡1（mod m_i）的一个解,所以学习中国剩余定理之前需要学习如何求解线性同余方程,不得不要的广告.

直接来一道模板题,曹冲养猪

#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL n,M=1;
LL a[15],b[15];
LL exgcd(LL a,LL b,LL &x,LL &y){
    if(b==0){x=1;y=0;return a;}
    LL d=exgcd(b,a%b,y,x);
    y-=x*(a/b);
    return d;
}
void Intchina(){
    LL x,y,ans=0;
    for(LL i=1;i<=n;i++){
        LL Mi=M/a[i];
        exgcd(Mi,a[i],x,y);
        ans=((ans+Mi*x*b[i])%M+M)%M;
    }
    printf("%lld\n",ans);
}
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&a[i],&b[i]);
        M*=a[i];
    }
    Intchina();
    return 0;
}