Submission #2125676

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e13;

long long N, A;

long long pw(long long a, int b) {
	long long ret = 1;
	for (int i = 1; i <= b; ++i) {
		if (ret > INF / a) return INF;
		ret *= a;
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> N >> A;
	if (N == 1) {
		return cout << 1 << endl, 0;
	}

	long long res = N;

	for (int i = 1; i <= 40; ++i) {
		// a[1] * a[2] * ... * a[i + 1] >= N
		// find min A * i + a[1] + a[2] + ... + a[i + 1]
		long long low = 1, high = N;
		while(low < high) {
			long long mid = ((low + high) >> 1);
			if (pw(mid, i + 1) >= N) high = mid; 
			else low = mid + 1;
		}

		for (int j = 0; j <= i; ++j) {
			// (low - 1)^j * (low)^(i + 1 - j) >= N
			if (j > 0 && low == 1) continue;
			long long cur = 1;
			for (int k = 1; k <= j; ++k) {
				if (cur <= INF / (low - 1)) cur *= (low - 1);
				else cur = INF;
			}
			for (int k = 1; k <= i + 1 - j; ++k) {
				if (cur <= INF / low) cur *= low;
				else cur = INF;
 			}
			if (cur >= N) res = min(res, A * i + (low - 1) * j + low * (i + 1 - j));
		}
	}

	cout << res << endl;
}

Submission Info

Judge Result