学步园

http://acm.hdu.edu.cn/showproblem.php?pid=1573

中国剩余定理

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>

using namespace std;

int a[ 11 ] , b[ 11 ] ;
#define INT __int64
int gcd( int a , int b )
{
	return b == 0 ? a : gcd( b , a % b ) ;
} 
int main()
{
	int Case ;
	int n , m ;
	scanf( "%d" , &Case ) ;
	while( Case-- )
	{
		memset( a , 0 , sizeof( a ) ) ;
		memset( b , 0 , sizeof( b ) ) ;
		scanf( "%d %d" , &n , &m ) ;
		for( int i = 0 ; i < m ; ++i )
			scanf( "%d" , &a[ i ] ) ;
		for( int i = 0 ; i < m ; ++i )
			scanf( "%d" , &b[ i ] ) ;
		int temp = 1 ;
		INT ans = 1 ; 
		for( int i = 0 ; i < m ; ++i )
		{
			temp = gcd( ans , a[ i ] ) ;
			ans = ans * a[ i ] / temp ;
		}
		int k = 0 ;
		int j ;
		for( int i = 1 ; i <= ans && i <= n ; ++i )
		{
			for( j = 0 ; j < m ; ++j )
				if( i % a[ j ] != b[ j ] )
					break ;
			if( j == m )
			{
				k = i ;
				break ;
			}
		} 
		if( k == 0 )
			printf( "0\n" ) ;
		else
		{
			int temp = n % ans ;
			if( temp >= k )
				k = n / ans  + 1 ;
			else
				k = n / ans ;
			printf( "%d\n" , k ) ;
		}
		
	}
	return 0 ;
}