Submission #857076

---

Source Code Expand

#include<iostream>

using namespace std;

typedef long long ll;

ll f(ll b,ll n){
	if(n<b)return n;
	return (f(b,n/b)+n%b);
}

ll bin(ll l,ll r,ll s,ll n){
	while(r-l>0){
		ll mi=(l+r)/2;
		if(f(mi,n)>s)l=mi+1;
		else r=mi;
	}
	if(f(r,n)==s)return r;
	return -1;
}
int main(){
	ll n,s;
	cin>>n>>s;
	ll ans=-1;
	ll t;
	if(n<s){
		cout<<-1<<endl;
		return 0;
	}
	for(t=2;t*t<=n;t++){
		if(f(t,n)==s){
			cout<<t<<endl;
			return 0;
		}
	}
	ans=bin(t,n,s,n);
	if(ans!=-1){
		cout<<ans<<endl;
		return 0;
	}
	if(n==s)cout<<n+1<<endl;
	else cout<<-1<<endl;
}

Submission Info

Judge Result