Submission #994217

---

Source Code Expand

#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>

#define FOR(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
#define IFOR(i, a, b) for(int (i)=(a);(i)<=(b);(i)++)
#define RFOR(i, a, b) for(int (i)=(a);(i)>=(b);(i)--)

using namespace std;

long long power(long long n, long long p) {
	if (p == 0)
		return 1;
	long long res = 1;
	long long add = n;
	while (p > 0) {
		if (p & 1)
			res = (res * add);
		p >>= 1;
		add = add*add;
	}
	return res;
}

bool check(long long T, long long N, long long a) {
	// division
	FOR(k, 1, T / a) {
		long long m = (T - (k - 1)*a) / k;
		long long r = (T - (k - 1)*a) % k;
		if (m>0 && log(N) / log(m) < k) {
			return true;
		}
		long long res = power(m, k - r) * power(m + 1, r);
		if (res >= N)
			return true;
	}
	return false;

}


int main() {
	long long n, a;
	cin >> n >> a;

	long long lb = 0, ub = n;
	while (ub - lb > 1) {
		long long half = (lb + ub) / 2;
		if (check(half, n, a)) {
			ub = half;
		}
		else {
			lb = half;
		}
	}
	cout << ub << endl;
	return 0;
}

Submission Info

Judge Result