J - 猪的安家

Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d
& %I64u

Description

Andy和Mary养了很多猪。他们想要给猪安家。但是Andy没有足够的猪圈,很多猪只能够在一个猪圈安家。举个例子,假如有16头猪,Andy建了3个猪圈,为了保证公平,剩下1头猪就没有地方安家了。Mary生气了,骂Andy没有脑子,并让他重新建立猪圈。这回Andy建造了5个猪圈,但是仍然有1头猪没有地方去,然后Andy又建造了7个猪圈,但是还有2头没有地方去。Andy都快疯了。你对这个事情感兴趣起来,你想通过Andy建造猪圈的过程,知道Andy家至少养了多少头猪。

Input

输入包含多组测试数据。每组数据第一行包含一个整数n (n <= 10) – Andy建立猪圈的次数,解下来n行,每行两个整数ai, bi( bi <= ai <= 1000), 表示Andy建立了ai个猪圈,有bi头猪没有去处。你可以假定(ai, aj) = 1.

Output

输出包含一个正整数,即为Andy家至少养猪的数目。

Sample Input

3
3 1
5 1
7 2

Sample Output

16

解题:

先求出最小满足第一行的,如例题中3+1=4,再验证是否符合第二行。4%5!=1,所以再把4递加3,直到(4+3*x)%5==1。继续验证下一行,不过递加要变为3和5的最小公倍数,一直循环到n,最后的总的最小公倍数即是答案。

注意:1长度的限制,在OJ上,__int64 of VC is not ANSI, but you can use long long for 64-bit integer。本题要用long
long

注意:2 注意只有一组输入的情况 这样每个猪圈都是没猪的

#include<iostream>
using namespace std;
int n;
long long a[11],b[11];
long long gcd[11];
void getgcd(){
gcd[1]=a[1];
for(int t=2;t<=n;t++){
long long x=gcd[t-1],y=a[t],z;
while(1){
z=x%y;
if(z==0){
gcd[t]=gcd[t-1]*a[t]/y;
break;
}
x=y;
y=z; }
} } int main(){ long long sum;//记得都用long long 用long也会错
while(cin>>n){
sum=0;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
getgcd();
sum=b[1];//注意这里 如果换成<span style="font-family: Arial, Helvetica, sans-serif;">sum=a[1]+b[1]就会错因为可能是一组的情况那么就是输出b[1]</span>
for(int j=1;j<=n;j++){ while(1){ if(sum%a[j]==b[j])break;
else sum+=gcd[j-1];
}
}
cout<<sum<<endl;
}
return 0;
}

另外一个:思路一样

#include<iostream>
using namespace std;
int main()
{
long long int n,a,b,c,d,i;
while(cin>>n)
{
cin>>a>>b;
//b=b+a;
for(i=1;i<n;i++)
{ cin>>c>>d;
while(b%c!=d)
b+=a;
a*=c;
}
cout<<b<<endl;
}
return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

05-11 22:52