题解 P1495 【曹冲养猪】

· · 题解

蒟蒻不会 CRT，但我们可以使用枚举来切掉这道水题，因此只需要小学五年级的水平。

如何枚举？如果只有两组同余式，求解最直接的思路就是从小到大枚举满足其中一个同余式的所有数直到找到满足另一个同余式的。更具体地，从余数出发，不断加上该同余式所对应的模数，当累加的结果满足另一个同余式时即为我们所求的最小值。

比如说样例中的3 1 5 1，满足第一个同余式的最小数为 1，然后不断加 3，加五次后得到数 16，满足第二个同余式，答案即为 16。这一过程用循环就可以实现。

得到了两组同余式的解法，我们推广一下即可，n 组同余式可从前往后，每次取前一次得到的最小数与本同余式进行运算，循环 n-1 次便可得出答案。

比如，对于题目中给出的样例：

3
3 1
5 1
7 2

首先取前两个同余式，根据上文所述的过程得到满足前两组同余式的最小值为 16，再在这个最小值的基础上引入第三个同余式，每次增加 3 和 5 的最小公倍数 15，由于 16 已经满足第三个同余式，不需要累加。得到答案为 16。

复杂度至多是 O(\sum a_i)，即模数之和，完全可过。

ok，你们最期待的代码来了：

#include<iostream>
#include<algorithm>
using namespace std;
struct pig{
    int a1,b1;
}a[11];//定义结构体存储a与b
int gcd(int x,int y){//公约数函数，用来求每一次循环累加的值
    if(x%y==0) return y;
    else return gcd(y,x%y);
}
int main(){
    long long n,ans,sum=1;//数据较大用longlong
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i].a1>>a[i].b1;
    }
    ans=a[1].b1;//初始化最小值
    for(int i=1;i<n;++i){//开始循环
        sum=sum*a[i].a1/gcd(sum,a[i].a1);//sum为累加的值
        while(ans%a[i+1].a1!=a[i+1].b1){//循环条件
            ans+=sum;
        }
    }
    cout<<ans;
    return 0;
}

祝愿大家 AC，RP++。