Submission #856074

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <cstdio>
#include <cstring>
using namespace std;

const int64_t small = 1000000;

int f(int b, int64_t n)
{
    int ret = 0;
    while (n > 0) {
        ret += n % b;
        n /= b;
    }
    return ret;
}

int main()
{
    int64_t n, s;
    cin >> n >> s;

    for (int b = 2; b < small; b++) {
        if (s == f(b, n)) {
            cout << b << endl;
            return 0;
        }
    }

    // if (small > n) {
    //     cout << -1 << endl;
    //     return 0;
    // }

    int64_t ans = -1;
    if (n == s) ans = n + 1;

    for (int64_t msb = 1; msb * msb <= n; msb++) {
        int64_t hi_b = n / msb;
        int64_t lo_b = n / (msb + 1) + 1;

        if (hi_b < small) break;
        if (s - msb < 0) break;

        int64_t st_s = n % hi_b;
        int64_t ed_b = n % lo_b;

        // [msb + st_s, .. msb + st_s + msb, ... msb + ed_b]

        if ((s - msb - st_s) % msb == 0 &&
            (s - msb) >= st_s && (s - msb) <= ed_b) {
            // cerr << "** ok: " << hi_b - ((s - msb - st_s) / msb) << endl;
            ans = hi_b - ((s - msb - st_s) / msb);
        }
    }

    cout << ans << endl;

    return 0;
}

Submission Info

Judge Result