问题 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;
}