1402.cpp

Andy和Mary养了很多猪。他们想要给猪安家。但是Andy没有足够的猪圈

// FZU.cpp : Defines the entry point for the console application.
//
#include<stdio.h>
long long ext_gcd(long long a,long long b,long long *x,long long *y)                 
{                                                                                                                                                                                                
  long long t,d;                                                                                  
  if(b==0)
  {
	  *x=1;
	  *y=0;
	  return a;
  }                    
  d=ext_gcd(b,a%b,x,y); 
  t=*x;     
  *x=*y; 
  *y=t-a/b*(*y);
  return d;                                       
} 
long long China(int b[],int w[],int k)
{ 
	int i; 
    long long d,x,y,m,n=1,a=0;
    for(i=0;i<k;i++)
		n*=w[i];                                    
    for(i=0;i<k;i++) 
	{                                          
         m=n/w[i];                                                                                                      
         d=ext_gcd(w[i],m,&x,&y); 
		 a=(a+y*m*b[i])%n;
	} 
    if (a>0)return a;                                                
    else return(a+n);                                         
}                                  
int main()
{
    int i,n,a[10],b[10];
	long long s;
	while(scanf("%d",&n)!=EOF)
	{
		for(i=0;i<n;i++)
			scanf("%d %d",&a[i],&b[i]);
		s=China(b,a,n);
		printf("%lld\n",s);
	}
	return 0;
}