程序园
     html  css  js  c++  java  常见问题

hdu1573-X问题

时间: 2022-08-06 21:27:50
                                        
    <p>http://acm.hdu.edu.cn/showproblem.php?pid=1573</p>

中国剩余定理

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

发表评论