Submission #856015

---

Source Code Expand

#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define PB push_back
#define MP make_pair
#define MOD 1000000007LL
#define endl "\n"
const ll UNDEF = -1;
const ll INF=1e18;
template<typename T> inline bool chkmax(T &aa, T bb) { return aa < bb ? aa = bb, true : false; }
template<typename T> inline bool chkmin(T &aa, T bb) { return aa > bb ? aa = bb, true : false; }
ll f(ll b,ll n) {
	if (n<b) return n;
	else return f(b,n/b)+(n%b);
}
ll solve(ll n, ll s) {
	{
		ll lim=sqrt(n)+5;
		for (ll b=2;b<=lim;b++) {
			if (f(b,n)==s) return b;
		}
	}
	{
		ll lim=sqrt(n)+5;
		ll ans=INF;
		for (ll x=1;x<=lim;x++) {
			ll y=s-x;
			if (y<0) continue;
			ll lhs=n-y;
			if (lhs%x==0) {
				ll b=lhs/x;
				//if (x==1) printf("ddx:%lld lhs:%lld b:%lld\n",x,lhs,b);
				if (b>=lim&&x<b&&y<b) {
					//printf("x:%lld lhs:%lld b:%lld\n",x,lhs,b);
					chkmin(ans,b);
				}
			}
		}
		if (n==s) chkmin(ans,n+1);
		if (ans>=INF) return -1;
		return ans;
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	ll n,s; cin>>n>>s;
	cout<<solve(n,s)<<endl;
}

Submission Info

Judge Result