Submission #994264

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/
ll n, a;
ll dp[2222222];
ll solve(ll t)
{
	if (dp[t] >= 0) return dp[t];
	ll res = INF;
	FOR(i, 2, n + 1)
	{
		if (t * i >= n)
		{
			chmin(res, ll(i));
			break;
		}
		chmin(res, i + a + solve(t * i));
	}
	return dp[t] = res;
}

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	cin >> n >> a;
	assert(n <= 1000000 && a <= 1000000);
	MS(dp, -1);
	if (n == 1) cout << 1 << endl;
	else cout << solve(1) << endl;
	return 0;
}

Submission Info

Judge Result