DよりEの方が簡単だった。
http://codeforces.com/contest/689/problem/C
問題
4人がチョコレートを食べる。
1人目がある正整数個食べた後、2~4人目は以降それぞれ直前のk倍(kは2以上の整数)の個数を食べる。
合計チョコレート数がn個以下の範囲で、4人の食べ方がm通りあったとする。
mからnの最小値を求めよ。
解法
f(n) := 合計チョコレート数がn個以下の食べ方の組み合わせ数
とする。f(n)は単調増加なので、f(n)=mを満たす最小のnを二分探索しよう。
f(n)はkを2からnの3乗根程度まで試せば求められる。
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; }
まとめ
変な問題。