Mike and Chocolate Thieves [Codeforces 361 : Div2 C]

問題

http://codeforces.com/contest/689/problem/C

以下を満たすa,kの個数がちょうどm個になるような自然数nを求めよ(無ければ-1)

• aは自然数
• kは自然数, 2 <= k
• ak^3 <= n

1 <= m <= 10^15

考察

1. これは知識がないと厳しいかも
2. わりかし二分探索感が出ている

• 10^15とかデカすぎ -> logn？？
• 今求めたいnだが、nが大きくなればなるほどmも大きくなる -> 単調増加
• 最小のnを出力せよ -> 境界線を知りたい

3. なので、ある自然数nについて条件を満たすa,kの個数をまあまあな速さで求められれば二分探索で解ける
4. ここのアルゴリズムはコード見たほうが多分早い

for( kを1から順番にk^3がnを越えるまで考える )
n / k^3 をすれば、aの候補数が分かるのでそれをカウントする

5. 二分探索はr=0,l=INFとしてr側はm個以下、l側はm個より大きいとすれば、最終的なrが答え

実装

http://codeforces.com/contest/689/submission/18928118

typedef long long ll;
ll m;
//-----------------------------------------------------------------
ll solve(ll x) {
	ll k = 2;
	ll ret = 0;
	while (k*k*k <= x) {
		ll d = x / (k*k*k);
		ret += d;
		k++;
	}
	return ret;
}
//-----------------------------------------------------------------
int main() {
	cin >> m;

	ll l = 0, r = 1LL << 60;
	while (l + 1 != r) {
		ll mid = (l + r) / 2;
		if (m <= solve(mid))
			r = mid;
		else
			l = mid;
	}
	
	if (solve(r) == m)
		printf("%I64d\n", r);
	else
		printf("-1\n");
}