问题 G: 曹冲养猪

问题 G: 曹冲养猪

时间限制: 1 Sec  内存限制: 128 MB
提交: 122  解决: 39
[提交][状态][讨论版][命题人:150112200121][Edit] [TestData]

题目链接：http://acm.ocrosoft.com/problem.php?cid=1703&pid=6

题目描述

自从曹冲搞定了大象以后，曹操就开始琢磨让儿子干些事业，于是派他到中原养猪场养猪，可是曹冲很不高兴，于是在工作中马马虎虎，有一次曹操想知道母猪的数量，于是曹冲想狠狠耍曹操一把。

举个例子，假如有 16 头母猪，如果建了 3 个猪圈，剩下 1 头猪就没有地方安家了；如果建造了 5 个猪圈，但是仍然有 1 头猪没有地方去；如果建造了 7 个猪圈，还有 2头没有地方去。你作为曹总的私人秘书理所当然要将准确的猪数报给曹总，你该怎么办？

输入

第一行包含一个整数 n，表示建立猪圈的次数；

接下来 n 行，每行两个整数 ai,bi，表示建立了 ai 个猪圈，有 bi 头猪没有去处。你可以假定 ai,aj 互质。

对于全部数据，1≤n≤10,1≤bi≤ai≤1000。

输出

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

样例输入

3

3 1

5 1

7 2

样例输出

16

思路：模板题，套板子

代码：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

ll n, m = 1, x, y, ans, al[1005], bl[1005];

ll exgcd(ll a, ll b, ll &x, ll &y) //扩展欧几里得定理+裴蜀定理，求解ax+by=d的一组解（x,y），d=gcd（a,b）

{

    if (b == 0) x = 1, y = 0;

    else {

         exgcd(b, a%b, y, x);//利用辗转相除法（a,b）=(a,a-b)=(a,a%b)

         y -= x * (a / b);

    }

}

int main() {

    cin >> n;

    for (int i = 1; i <= n; i++)

    {

         cin >> al[i] >> bl[i];

         m *= al[i];

    }

    //同余方程组最小负整数解的算法实现

    for (int i = 1; i <= n; i++) {

         ll k = m / al[i];

         exgcd(k, al[i], x, y);

         ans = (ans + bl[i] * x*k) % m;

    }

    cout << (ans + m) % m;

}