OI XXIX - arm (Alt)

// https://szkopul.edu.pl/problemset/problem/gxeCvLD1xW1t-Y33bbC0n3wZ/statement/

#include <bits/stdc++.h>

constexpr uint64_t LIMIT = 4000000000000000000ULL;
constexpr int64_t INF = 4e18;

[[nodiscard]] inline uint64_t mul_safe(uint64_t a, uint64_t b) noexcept {
    if (a == 0 || b == 0) return 0;
    if (a > LIMIT / b) return LIMIT;
    return a * b;
}

[[nodiscard]] inline uint64_t pow_safe(uint64_t base, uint32_t exp) noexcept {
    uint64_t res = 1;
    while (exp > 0) {
        if (exp & 1) res = mul_safe(res, base);
        base = mul_safe(base, base);
        exp >>= 1;
    }
    return res;
}

[[nodiscard]] inline uint64_t integer_kth_root(uint64_t n, uint32_t k) noexcept {
    if (k == 1) return n;
    uint64_t r = static_cast<uint64_t>(std::pow(static_cast<double>(n), 1.0 / k));
    if (r < 1) r = 1;
    while (pow_safe(r + 1, k) <= n)
        ++r;
    while (r > 1 && pow_safe(r, k) > n)
        --r;
    return r;
}

[[nodiscard]] inline bool is_ge(uint64_t r, uint32_t k, int32_t p, uint64_t n) noexcept {
    if (p < 0) return false;
    if (p >= static_cast<int32_t>(k)) return pow_safe(r + 1, k) >= n;
    uint64_t p1 = pow_safe(r + 1, static_cast<uint32_t>(p));
    uint64_t p2 = pow_safe(r, k - static_cast<uint32_t>(p));
    return mul_safe(p1, p2) >= n;
}

int64_t solve(int64_t n, int64_t a, int64_t b) {
    if (n <= 1) return 0;

    int64_t ans = INF;

    if (b == 0 || (n - 1) <= (INF - a) / b) {
        ans = a + b * (n - 1);
    }

    for (uint32_t k = 2; k <= 60; ++k) {
        uint64_t r = integer_kth_root(static_cast<uint64_t>(n), k);

        int32_t p = 0;
        if (r == 1) {
            p = 64 - __builtin_clzll(static_cast<uint64_t>(n - 1));
        } else {
            long double num = std::log(static_cast<long double>(n)) - static_cast<long double>(k) * std::log(static_cast<long double>(r));
            long double den = std::log(static_cast<long double>(r + 1)) - std::log(static_cast<long double>(r));
            p = static_cast<int32_t>(std::floor(num / den));
        }

        p = std::max(0, std::min(static_cast<int32_t>(k), p));

        while (p > 0 && is_ge(r, k, p - 1, static_cast<uint64_t>(n))) {
            --p;
        }
        while (p <= static_cast<int32_t>(k) && !is_ge(r, k, p, static_cast<uint64_t>(n))) {
            ++p;
        }

        if (p <= static_cast<int32_t>(k)) {
            int64_t mult_sum = static_cast<int64_t>(k) * (static_cast<int64_t>(r) - 1) + p;
            if (b == 0 || mult_sum <= (INF - static_cast<int64_t>(k) * a) / b) {
                int64_t cost = static_cast<int64_t>(k) * a + b * mult_sum;
                ans = std::min(ans, cost);
            }
        }
    }

    return ans;
}

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int64_t n, a, b;
    std::cin >> n >> a >> b;
    std::cout << solve(n + 1, a, b) << '\n';

    return 0;
}