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

33 15 17 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
       
        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];//注意这里 如果换成
        sum=a[1]+b[1]就会错因为可能是一组的情况那么就是输出b[1]		for(int j=1;j<=n;j++){						while(1){								if(sum%a[j]==b[j])break;				else sum+=gcd[j-1];			}		}		cout<
        
         <
        
       

另外一个：思路一样 

#include
       
        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
        
         >c>>d;		while(b%c!=d)			b+=a;		a*=c;		}		cout<
         <
        
       

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