Cod sursa(job #1164666)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 2 aprilie 2014 11:20:42
Problema Dtcsu Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include<fstream>
#include<bitset>

using namespace std;

#define nr_linii 276997

FILE*f = fopen("dtcsu.in" , "r");
FILE*g = fopen("dtcsu.out" , "w");

int fact[] = { 0 , 2 , 3 , 5 , 7 , 11 };
long long n , nr , aux;
char sir[30];
int sol;

bitset< 1<<22 >H1;
bitset< 1<<21 >H2;

inline void get_nr( long long &nr ){
    fgets( sir , 30 , f );
    nr = 0;
    int k = 0;
    while( sir[k] >= '0' && sir[k] <= '9' ){
        nr = nr*10 + sir[k] - '0';
        k++;
    }
}

inline long long hash1( long long nr ){
    return nr >> 23LL & ((1LL << 22) - 1);
}

inline long long hash2( long long nr ){
    return nr >> 3LL & ((1LL << 21) - 1);
}

inline void read(){

    for( int i = 1 ; i <= nr_linii ; i++ ){
        get_nr( nr );
        H1[hash1(nr)] = true;
        H2[hash2(nr)] = true;
    }

}

inline bool verif( long long nr ){
    return H1[hash1(nr)] & H2[hash2(nr)];
}

int main(){

    read();

    get_nr( n );

    for( int i = 1 ; i <= n ; i++ ){
        get_nr( nr );

        if( verif( nr ) ){

            while( (nr & (-nr)) > 1 )
                nr /= (nr & (-nr));

            while( nr > 1 && (( aux = nr/15 ) * 15 == nr) ){
                nr = aux;
            }

            for( int j = 2 ; j <= 5 ; j++ ){
                while( nr > 1 && (( aux = nr/fact[j] ) * fact[j] == nr) ){
                        nr = aux;
                }
            }
            if( nr == 1 ){
                sol++;
            }
        }
    }

    fprintf( g , "%d" , sol );

    return 0;
}