Cod sursa(job #1032806)

Utilizator fmins123FMI No Stress fmins123 Data 16 noiembrie 2013 02:31:56
Problema Dtcsu Scor Ascuns
Compilator cpp Status done
Runda Marime 1.51 kb
#include <fstream>
#include <algorithm>
#include <string>
#include <bitset>
#include <vector>
#include <functional>

using namespace std;

int Q;
char num[32];
bitset< (1<<21) > bitArrayA;
bitset< (1<<22) > bitArrayB;

inline int hash1(const long long &x) {
	return x & ((1LL << 21) - 1);
}

inline int hash2(const long long &x) {
	return x >>	23LL & ((1LL << 22) - 1);
}

inline bool query(const long long &x) {
	return bitArrayA[hash1(x)] && bitArrayB[hash2(x)];
}

inline void update(const long long &x) {
	bitArrayA[hash1(x)] = true;
	bitArrayB[hash2(x)] = true;
}

inline void readSet() {
	for (int i = 0;i < 276997;i++) {
		fgets(num,32,stdin);
		long long value = 0;
		for(int i = 0;num[i] && num[i] != '\n';i++) {
			value = value*10 + (num[i] - '0');
		}
		update(value);
	}
}

inline void solve() {
	int ret = 0;
	const int fc[5] = {2,3,5,7,11};
	scanf("%d\n",&Q);
	for (int i = 0;i < Q;i++) {
		fgets(num,32,stdin);
		long long value = 0;
		for(int i = 0;num[i] != '\0' && num[i] != '\n';i++) {
			value = value * 10 + (num[i] - '0');
		}

		if (query(value)) {
			while ( (value & 1) == 0) value >>= 1;
			while ( 1LL*(value / 15 ) * 15 == value) value /= 15;
			for (int k = 1;k < 5 && value > 1;k++) {
				while (value > 1 &&  1LL*(value/fc[k]) * fc[k] == value) value /= fc[k];
			}

			ret += (value == 1);
		}
	}
	printf("%d\n",ret);
}

int main()
{
	freopen("dtcsu.in","r",stdin);
	freopen("dtcsu.out","w",stdout);
	readSet();
	solve();
	return 0;
}