题解：AT_arc060

分类讨论：
当 $(n)_b$ 是一位数时，必有 $f(b,n)=n$。这一部分可以特判掉（$n \le s$）。
当 $(n)_b$ 为至少三位的数，$n^2 > b$。此时一定有 $b \le \sqrt{n}$。循环解决。
否则，$(n)_b$ 是两位数，则：

$$n=bk+p$$

$$s=k+p$$

$$n-s=(b-1)k$$

因此可以枚举 $(n-s)$ 的因数进行判断。
总时间复杂度 $O(\sqrt{n})$，可以通过。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


#include<bits/stdc++.h>
using namespace std;
long long f(long long b,long long n){
	if(n<b)return n;
	return f(b,n/b)+n%b;
}
int main(){
	long long n,s;
	scanf("%lld%lld",&n,&s);
	if(n<s){
		puts("-1");
		return 0;
	}
	if(n==s){
		printf("%lld",n+1);
		return 0;
	}
	long long x=sqrt(n)+1;
	for(long long i=2;i<=x;i++){
		if(f(i,n)==s){
			printf("%lld",i);
			return 0;
		}
    }
	long long ans=0;
	for(long long i=1;i<=x;i++){
		if((n-s)%i)continue;
		if(f((n-s)/i+1,n)==s)ans=(n-s)/i+1;
    }
	if(ans==0)puts("-1");
	else printf("%lld",ans);
}