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;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。