OI XXIX - arm (Alt2)

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

#include <bits/stdc++.h>

constexpr int64_t INF = 4e18;

bool pow_le(uint64_t x, int m, uint64_t N) {
    if (x <= 1) return true;
    uint64_t val = 1;
    for (int i = 0; i < m; ++i) {
        if (N / x < val) return false;
        val *= x;
    }
    return val <= N;
}

uint64_t get_S(uint64_t N, int m) {
    if (m == 1) return N;
    uint64_t S = static_cast<uint64_t>(std::pow(static_cast<double>(N), 1.0 / m));
    if (S < 1) S = 1;
    while (pow_le(S + 1, m, N))
        S++;
    while (S > 1 && !pow_le(S, m, N))
        S--;
    return S;
}

bool check_product(uint64_t S, int m, int k, uint64_t N) {
    uint64_t prod = 1;

    for (int i = 0; i < k; ++i) {
        if (S == 0) return false;
        if (prod > (N + S - 1) / S) return true;
        prod *= S;
    }

    for (int i = 0; i < m - k; ++i) {
        if (prod > (N + S) / (S + 1)) return true;
        prod *= (S + 1);
    }

    return prod >= N;
}

void solve() {
    int64_t n_in, a, b;
    std::cin >> n_in >> a >> b;

    uint64_t N = static_cast<uint64_t>(n_in) + 1;
    int64_t ans = INF;

    if (b == 0 || (N - 1) <= static_cast<uint64_t>((INF - a) / b)) {
        ans = a + static_cast<int64_t>(N - 1) * b;
    }

    for (int m = 2; m <= 60; ++m) {
        uint64_t S = get_S(N, m);

        for (int k = 0; k <= m; ++k) {
            if (check_product(S, m, k, N)) {
                int64_t copies = static_cast<int64_t>(S * m - k);

                if (b == 0 || copies <= (INF - static_cast<int64_t>(m) * a) / b) {
                    int64_t cost = static_cast<int64_t>(m) * a + copies * b;
                    ans = std::min(ans, cost);
                }
            }
        }
    }

    std::cout << ans << '\n';
}

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

    solve();

    return 0;
}