Codeforces ECR #050 : F. Relatively Prime Powers

時間ぎりぎりだった。
http://codeforces.com/contest/1036/problem/F

問題

正整数Xがエレガントであるとは、Xを素因数分解したとき各素因数の指数のGCDが2以上になるものを意味するものとする。
正整数Nに対し、N以下のエレガントな正整数の数を求めよ。

解法

まず以下を考える。
f(p,N) := 素因数の指数のGCDがpの約数になるN以下の正整数の集合

あいにくNは最大10^18と大きいので、f(2,N)は列挙できない。
そこで、を求めよう。
これは、まず前半の集合の和集合は愚直に総当たりし、その後平方数を取り除けばよい。
あとはN - |f(2,N)| - |g(N)|が解。

この問題では実際には多数のテストケースがあるが、|f(2,N)|は結局floor(√N)なので容易に求められる。
g(N)は、先にg(10^18)を作成しておき、lower_bound等で|g(N)|を求めればよい。

int T;
ll N;

vector<ll> C;

ll issq(ll V) {
	ll a=sqrt(V);
	if(a*a==V) return 1;
	if((a-1)*(a-1)==V) return 1;
	if((a+1)*(a+1)==V) return 1;
	return 0;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(ll a=2;a<=1000000;a++) {
		ll v=a*a*a;
		while(v<=1000000000000000000LL) {
			if(!issq(v)) C.push_back(v);
			if((double)v*a>2e18) break;
			v*=a;
		}
	}
	
	sort(ALL(C));
	C.erase(unique(ALL(C)),C.end());
	
	cin>>T;
	while(T--) {
		cin>>N;
		ll ret=N-(ll)sqrt(N+0.5)-(lower_bound(ALL(C),N+1)-C.begin());
		cout<<ret<<endl;
		
	}
}

まとめ

オーバーフローとかで変に手間取った。