Submission #857363

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#ifndef ONLINE_JUDGE
#define dbg(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;
#else
#define dbg(x)
#endif

#define X first
#define Y second

ll f(ll base, ll num){
    ll res = 0;
    while (num){
        res += num % base;
        num /= base;
    }
    return res;
}


int main(){
    std::ios_base::sync_with_stdio(false);
    ll n, s; cin >> n >> s;
    if (n == s) {
        cout << n + 1 << endl;
        return 0;
    }
    for (ll i = 2; i * i <= n; i++){
        if (f(i, n) == s){
            cout << i << endl;
            return 0;
        }
    }
    ll rt = sqrt(n);
    while (rt * rt < n) rt++;
    ll ans = LLONG_MAX;
    for (ll q = min(s, rt); q >= 1; q--){
        ll r = s - q;
        if ((n - r) % q == 0){
            ll b = (n - r) / q;
            if (r < b){
                ans = min(ans, b);
            }
        }
    }
    if (ans == LLONG_MAX) cout << -1 << endl;
    else cout << ans << endl;


    return 0;
}

Submission Info

Judge Result