中国剩余定理
#include#include #include #include #include using namespace std;int a[ 11 ] , b[ 11 ] ;#define INT __int64int 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 ;}