HackerRank University CodeSprint 5 : E. Cube-loving Numbers

考察ができれば実装は容易。
https://www.hackerrank.com/contests/university-codesprint-5/challenges/cube-loving-numbers

問題

正整数XがCube-lovingであるとは、2以上の正整数aを用いてと書けるものである。
正整数Nが与えられるので、N以下のCube-lovingな正整数の数を求めよ。

解法

包除原理の要領で解く。
以下を考える。

f(a) := N以下の正整数Xのうち、と書けるものの
g(a) := N以下の正整数Xのうち、と書けるもののうち、取りえるa'の最大値がaであるもの

解は　なので、g(i)を求めればよい。
f(i)、g(i)は以下の関係があるので、f(i)、g(i)を大きい順に求めていこう。

int T;
ll N;
ll cnt[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		ll ret=0;
		for(x=1000000;x>=2;x--) {
			cnt[x]=N/(1LL*x*x*x);
			for(y=x*2;y<=1000000;y+=x) cnt[x]-=cnt[y];
			ret+=cnt[x];
		}
		cout<<ret<<endl;
		
	}
}

まとめ

今回難易度順おかしく感じた。
これ(消えちゃったけど)Dより難しくない…？