Submission #858767

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const long long INF = 0x3f3f3f3f3f3f3f3fLL;

long long n , s , n_s , t , rem , ans;
int tmp , cnt;

bool judge(long long b) {//判断b进制下的各位和是否等于s
    rem = n;
    t = 0;
    while(rem > 0) {
        t += rem % b;
        rem /= b;
    }
    return t == s;
}

void solve() {
    tmp = sqrt(0.0 + n);
    n_s = n - s;
    ans = (n == s ? n + 1 : INF);
    for(int i = 2 ; i <= tmp ;++i) {//枚举到sqrt(n)
        if(judge(i)) {
            ans = min(ans , (long long) i);
        }
        if(n_s % i == 0 && judge(n_s / i + 1)) {//枚举所有的大于sqrt(b)且是n-s的因子的数
            ans = min(ans , n_s / i + 1);
        }
    }
    printf("%lld\n" , ans == INF ? -1 : ans);
}

int main() {
    while(2 == scanf("%lld%lld", &n, &s)) {
        solve();
    }
    return 0;
}

Submission Info

Judge Result