Submission #994708

---

Source Code Expand

#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <numeric>
#include <list>
#include <assert.h>
#include <math.h>
#include <valarray>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <complex>
#include <list>

using namespace std;
typedef long long int LL;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

LL pow(LL a,LL b) {
	if (b == 1) {
		return a;
	}else
		if (b == 0) {
			return 1;
		}else
			if (b % 2 == 0) {
				return pow(a, (LL)(b / 2))*pow(a, (LL)(b / 2));
			}
			else {
				return a*pow(a, (LL)((b-1) / 2))*pow(a, (LL)((b - 1) / 2));
			}
}

int main()
{
	LL N, A;
	cin >> N >> A;
	LL cost = N;
	LL n = 2;
	
	LL Nsqrt = (LL)floor(sqrt(N));
	LL m = 0;
	LL k = 1;
	while (true) {
		if (n - m >= 0 && pow(Nsqrt, n - m)*pow(Nsqrt + 1, m) < N) {
			m++;
		}
		else {
			while (true) {
				if (n - m - k >= 0 && pow(Nsqrt, n - m - k)*pow(Nsqrt + 1, m)*pow(Nsqrt - 1, k) >= N) {
					k++;
				}
				else {
					k--;
					break;
				}
			}
			break;
		}
	}
	LL newcost = Nsqrt*(n-m-k)+ (Nsqrt + 1)*m+ (Nsqrt - 1)*k + A*(n - 1);
	if (newcost < cost) {
		cost = newcost;

		while (true) {
			n++;

			FOR(i, 1, Nsqrt) {
				if (pow(i,n) >= N) {
					Nsqrt = i-1;
					break;
				}
			}
			m = 0;
			k = 1;
			while (true) {
				if (n-m>=0&&pow(Nsqrt, n - m)*pow(Nsqrt + 1, m) < N) {
					m++;
				}
				else {
					while (true) {
						if (Nsqrt!=1&&n - m - k >= 0 && pow(Nsqrt, n - m - k)*pow(Nsqrt + 1, m)*pow(Nsqrt - 1, k) >= N) {
							k++;
						}
						else {
							k--;
							break;
						}
					}
					break;
				}
			}
			newcost = Nsqrt*(n - m - k) + (Nsqrt + 1)*m + (Nsqrt - 1)*k + A*(n - 1);
			if (newcost >= cost) {
				break;
			}
			else {
				cost = newcost;
			}
			if (Nsqrt == 1) { break; }
		}
	}

	cout << cost << endl;
	
}

Submission Info

Judge Result