toj_2931.cpp

来自「Tianjin University Online Judge 的80多道题目 」· C++ 代码 · 共 99 行

#include<cstdio>
#include<cmath>
#define MINNUM 1e-10
#define MAXLEN 1010
struct Fact
{
    int aFact[ 100 ];
    int nOfFact;
};
    
int  note[ MAXLEN ] , nOfNote;
double x;
Fact xFact;

void findFact( int n )
{
    int static i;
    xFact.nOfFact = 0;
    
    for( i = 3; i * i <= n; i++ )
    {
        if( n % i == 0 ){
            xFact.aFact[ xFact.nOfFact++ ] = i;
            while ( n % i == 0 ){
                n /= i;
            }
        }
    }
}

int gcd( int a , int b )
{
    int static  temp;
    while ( b != 0 ){
        temp = b;
        b = a % b;
        a = temp;
    }
//    printf( "a = %d\n" , a );
    return a;
}

        
    
int main()
{
    freopen( "c.in" , "r" , stdin );
    freopen( "toj_2931_out.txt" , "w" , stdout );
    
    int i , j ,nOfCase , xDenominator , xNumerator , fact5 , gcdForAll;
    
    scanf( "%d" , &nOfCase );
    for( ; nOfCase > 0 ; nOfCase-- ){
        scanf( "%lf" , &x );
        scanf( "%d" , &nOfNote );
        for( i = 0; i < nOfNote; i++ )
            scanf( "%d" , &note[ i ] );
        xDenominator = int (x * 100 + MINNUM);
//        printf( "xd = %d\n" , xDenominator );
        fact5 = 0;
        while ( xDenominator % 5 == 0 && fact5 < 2 ){
            xDenominator /= 5;
            fact5++;
        }
        if( fact5 != 2 )
            printf( "no\n" );
        else{
            while ( xDenominator % 2 == 0 ){

  //              printf( "x = %d\n" , xDenominator );
                
                xDenominator /= 2;
                }
//            findFact( xDenominator );
            gcdForAll = 1;
            
            for( i = 0; i < nOfNote; i++ ){
                gcdForAll = gcd ( gcdForAll , note[ i ] );
                
            }
            while ( gcdForAll % 2 == 0 )
                gcdForAll /= 2;
            if ( xDenominator  % gcdForAll == 0 )
                printf( "yes\n" );
            else
                printf( "no\n" );
        }
    }
    return 0;
}