hdu1573-X問題

中國剩余定理

 
#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 ;  
}