题解 P1495 【曹冲养猪】

Dog_Two · 2018-02-02 19:58:13 · 题解

题面一如既往地亲切和蔼……仿佛生怕选手不知道这是一道中国剩余定理的裸题。

中国剩余定理是啥……相信也不需要多做介绍了，这里需要简单提醒大家，中国剩余定理可以采用的充要条件是模数互质（在本题中也就是猪圈数目互质）

好的，切回正题。

蒟蒻我曾经帮一位队友做了一份课件，里面是讲解同余问题的（当然包括中国剩余定理）但我的队友们实在难以接受这样复杂的程序。所以我给他们归纳了几句并不严谨的“技巧”。

• ①对于数字 W[i]，求出（即相乘）其他所有数字的最小公倍数M;
• ②在M所有整数倍中，找到一个模B[i]为1的数字N[i];
• ③对所有N[i]求和，不断对所有W[i]的最小公倍数取模;
• ④最后剩下的一个不能减的正数即为所求。

根据以上的顺序，我们不难写出一个看起来几乎无异于暴力枚举的程序，但事实上，它的确是正确的：

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long LLi;
//所有int都被换成了long_long ，所以视觉效果并不好 
LLi n;
LLi W[20],B[20];
LLi sum;
LLi CRT(){
    LLi tot=1;
    LLi res=0;
    for(LLi i=0;i<sum;i++) tot*=W[i];
    //注意，数组下标从0开始 
    for(LLi i=0;i<sum;i++){
        LLi m=tot/W[i];
        for(LLi j=1;;j++){
            if((m*j)%W[i]==1){
                res+=m*j*B[i];
                res%=tot;
                break;
            }
        }
    }
    return res>0?res:res+tot;
}
int main(){
    cin>>n; sum=n;
    //这里完全可以把变量sum略去，在CRT()里把所有sum替换成n 
    for(LLi i=0;i<n;++i) scanf("%lld%lld",&W[i],&B[i]);
    cout<<CRT();
    return 0;
}

另附送一份ex_gcd+CRT的代码可以当板子用

#include<bits/stdc++.h>
using namespace std;
long long n;
long long Wi[20],Bi[20];
long long ext_gcd(long long a,long long b,long long &x,long long &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    long long d=ext_gcd(b,a%b,x,y);
    long long temp=x;x=y,y=temp-a/b*y;
    return d;
}
long long CRT(long long *W,long long *B,long long k/*方程组数*/){
    long long x,y,a=0,m,n=1;
    for(long long i=0;i<k;i++) n*=W[i];
    for(long long i=0;i<k;i++){
        m=n/W[i];
        ext_gcd(W[i],m,x,y);
        a=(a+y*m*B[i])%n;
    }
    return a>0?a:a+n;
}
int main(){
    cin>>n;
    for(long long i=0;i<n;++i) scanf("%lld%lld",&Wi[i],&Bi[i]);
    cout<<CRT(Wi,Bi,n);
    return 0;
}