问题 G: Digit Sum II

时间限制: 1 Sec  内存限制: 128 MB

提交: 36  解决: 11

[][][][命题人:]

题目描述

For integers b(b≥2) and n(n≥1), let the function f(b,n) be defined as follows:

·f(b,n)=n, when n<b

·f(b,n)=f(b,floor(n⁄b))+(n mod b), when n≥b

Here, floor(n⁄b) denotes the largest integer not exceeding n⁄b, and n mod b denotes the remainder of n divided by b.

Less formally, f(b,n) is equal to the sum of the digits of n written in base b. For example, the following hold:

·f(10,87654)=8+7+6+5+4=30

·f(100,87654)=8+76+54=138

You are given integers n and s. Determine if there exists an integer b(b≥2) such that f(b,n)=s. If the answer is positive, also find the smallest such b.

Constraints

1≤n≤1011

1≤s≤1011

n,s are integers.

输入

The input is given from Standard Input in the following format:

n

s

输出

If there exists an integer b(b≥2) such that f(b,n)=s, print the smallest such b. If such b does not exist, print -1 instead.

样例输入

8765430

样例输出

10 题意：已知 n,s ，n 转化成b 进制数，且各位数之和为s, 求这个最小的b ,若不存在，输出 -1

             

 

c++ code:

#include 
     
      using namespace std;typedef long long ll;ll sum(ll n,ll b){	ll ans=0;	while(n)	{		ans+=n%b;		n/=b;	}	return ans;}int main(){		ll n,s;	scanf("%lld%lld",&n,&s);	if(n==s)		printf("%lld\n",n+1);	else	{		for(ll i=2;i<=sqrt(n)+1;i++)		{			ll b=i;			if(sum(n,b)==s)			{				return 0*printf("%lld\n",b);				return 0;			}		}		if(n-s>1)		{			for(ll i=sqrt(n);i;i--)			{				ll b=(n-s)/i+1;				if(sum(n,b)==s)				{					printf("%lld\n",b);					return 0;				}			}		}		puts("-1");	}	return 0;}