Codeforces #361 Div2 C. Mike and Chocolate Thieves

DよりEの方が簡単だった。
http://codeforces.com/contest/689/problem/C

問題

４人がチョコレートを食べる。
1人目がある正整数個食べた後、2～4人目は以降それぞれ直前のk倍(kは2以上の整数)の個数を食べる。

合計チョコレート数がn個以下の範囲で、４人の食べ方がm通りあったとする。
mからnの最小値を求めよ。

解法

f(n) := 合計チョコレート数がn個以下の食べ方の組み合わせ数
とする。f(n)は単調増加なので、f(n)=mを満たす最小のnを二分探索しよう。
f(n)はkを2からnの３乗根程度まで試せば求められる。

ll M;

ll getnum(ll v) {
	ll ret=0;
	for(ll a=2;a*a*a<=v;a++) ret += v/(a*a*a);
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>M;
	ll ret=0;
	for(i=59;i>=0;i--) if(getnum(ret+(1LL<<i))<M) ret+=(1LL<<i);
	ret++;
	if(getnum(ret)==M) cout<<ret<<endl;
	else cout<<-1<<endl;
	
}

まとめ

変な問題。