题解 P1495 【曹冲养猪】

· · 题解

刚刚学完Exgcd和中国剩余定理，写一篇题解。

题目大意已经很明确了，而且还告诉我们可以假定猪圈数（模数）互质，显然套板子咯

一共n个线性同余方程组，求解。

设M为所有模数之积，模数分别为m_i，M_i=M/m_i,t_i是方程M_it_i同余1的一个解。则对于这个方程组有整数解，且方程组的解为：

显然对于$t_i$，$Exgcd$暴力求解即可。对于$M$，直接预处理，$M_i$什么的$O(1)$算出即可。 注意上文的几个定义： - $a_i$为方程组$x$同余$a_i$ $mod$ $m_i$中的$a_i$。 - $t_i$是一组线性同余方程的解。 - 在本题中，猪圈数$=$模数，且模数互质是中国剩余定理的充要条件 本题得解。 $Code: 
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long LL;
LL n,a[500000],b[500000],M=1;
inline void Exgcd(LL a,LL b,LL &d,LL &x,LL &y){
    if(!b){d=a;x=1;y=0;}
    else{
        Exgcd(b,a%b,d,x,y);
        LL t=x;x=y;y=t-(a/b)*y;
    }
}
inline LL IntChina(){
    LL Ans=0,Mi,x,y,d;
    for(LL i=1;i<=n;++i){
        Mi=M/a[i];
        Exgcd(Mi,a[i],d,x,y);
        Ans=((Ans+Mi*x*b[i])%M+M)%M;
    }return (Ans+M)%M;
}
int main(){
    scanf("%lld",&n);
    for(LL i=1;i<=n;++i){
        scanf("%lld%lld",&a[i],&b[i]);
        M*=a[i];
    }
    printf("%lld\n",IntChina());
    return 0;
}

对于模数不互质的方程组，我们有拓展中国剩余定理求解。