问题 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≤biai≤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;

}