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

chu_yh · 2025-03-07 21:09:50 · 题解

废话：同一个机房的题解就要扎堆站

欢迎踩博客

@DX3906_ourstar 大佬没发出来的 PPT（看网页地址）

中国剩余定理是数论中的一个重要定理，用于解决一组同余方程的问题。

定理内容

给定一组两两互质的正整数 n_1,n_2,\dots,n_k，以及任意整数 a_1,a_2,\dots,a_k，存在一个整数 x，满足以下同余方程组：

并且，这个解 x 在模 N=n_1 n_2\dots n_k 下是唯一的。

证明

1. 存在性：

   • 由于 n_1, n_2, \dots, n_k 两两互质， N = n_1 n_2 \dots n_k 。
   • 对于每个 i，计算 N_i=N / n_i。由于 n_i 与 N_i 互质，存在整数 m_i 使得 m_i N_i\equiv 1 \pmod{n_i}。
   • 令 x=\sum_{i=1}^k a_i m_i N_i。对于每个 i，x\equiv a_i m_i N_i\equiv a_i\cdot 1\equiv a_i\pmod{n_i}，因此 x 是方程组的解。

2. 唯一性：

   • 假设 x 和 y 都是方程组的解，则 x \equiv y \pmod{n_i} 对所有 i 成立。
   • 由于 n_i 两两互质，x\equiv y\pmod{N}，即 x 和 y 在模 N 下相同。

中国剩余定理通过将大模数问题分解为小模数问题，简化了计算过程。

实现

扩展欧几里得算法求逆元

乘法逆元是数论中的一个重要概念。给定整数 a 和模数 m ，如果存在整数 x 使得 a x \equiv 1 \pmod{m} ，则称 x 是 a 在模 m 下的乘法逆元，记作 a^{-1} 。

1. 使用欧几里得算法求 \gcd(a, m) 。
2. 如果 \gcd(a, m) \neq 1 ，则 a 在模 m 下没有逆元。
3. 如果 \gcd(a, m) = 1 ，则通过扩展欧几里得算法求出 x 和 y ，使得：

此时， x 就是 a 在模 m 下的逆元。

代码

void exgcd(int a,int b,int &X,int &Y){
    if(!b){X=1,Y=0;return ;}
    exgcd(b,a%b,X,Y);
    int t=X;
    X=Y;
    Y=t-a/b*X;
}

完整代码

#include<bits/stdc++.h>
#define int __int128
using namespace std;
int n,m[11],r[11],c,M=1,x,y,ans;

void exgcd(int a,int b,int &X,int &Y){
    if(!b){X=1,Y=0;return ;}
    exgcd(b,a%b,X,Y);
    int t=X;
    X=Y;
    Y=t-a/b*X;
}

signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&m[i],&r[i]);
        M*=m[i];
    }
    for(int i=1;i<=n;i++){
        c=M/m[i];
        exgcd(c,m[i],x,y);
        ans=((ans+c*x*r[i])%M+M)%M;
    }
    printf("%lld",ans);
    return 0;
}