[数据结构与算法]【模板】中国剩余定理(CRT)/曹冲养猪

题目描述

自从曹冲搞定了大象以后，曹操就开始捉摸让儿子干些事业，于是派他到中原养猪场养猪，可是曹冲满不高兴，于是在工作中马马虎虎，有一次曹操想知道母猪的数量，于是曹冲想狠狠耍曹操一把。举个例子，假如有 16 头母猪，如果建了 3 个猪圈，剩下 1 头猪就没有地方安家了。如果建造了 5 个猪圈，但是仍然有 1 头猪没有地方去，然后如果建造了 7 个猪圈，还有 2 头没有地方去。你作为曹总的私人秘书理所当然要将准确的猪数报给曹总，你该怎么办？

输入格式

第一行包含一个整数 n——建立猪圈的次数，接下来 n 行，每行两个整数 a，b， 表示建立了 a个猪圈，有 b头猪没有去处。你可以假定 a?，a互质。

输出格式

输出包含一个正整数，即为曹冲至少养母猪的数目。

输入输出样例

输入 #1

3
3 1
5 1
7 2

输出 #1

16

说明/提示

1≤n≤10，0≤bi?<ai?≤100000

#include<bits/stdc++.h>
using namespace std;
// int gcd(int a,int b)
// {
//     if(b==0)
//         return a;
//     else
//         gcd(b,b%a);
// }

// int f(int a,int b)
// {
//     // 最小公倍数=两整数的乘积÷最大公约数
//     int temp;
//     temp=(a*b)/gcd(a,b);
//     return temp;
// }

int n,a[16],m[16];
long long int t[16];

int main()
{
    while(cin>>n){
        long long int sum=1;
        for(int i=0;i<n;i++){
            cin>>a[i]>>m[i];
            sum*=a[i];
        }
        long long int ans=0;
        for(int i=0;i<n;i++)
            t[i]=sum/a[i];
        for(int i=0;i<n;i++)
        //0x7f7f7f7f比所有变量的最大值都大 
            for(long long int j=t[i];j<=0x7f7f7f7f7f7f;j+=t[i])
                if(j%a[i]==1){
                    ans+=j*m[i];
                    break;
                }
        ans=ans%sum;
        cout<<ans<<endl;
    }
}