考察ができれば実装は容易。
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より難しくない…?