这题一眼二分，我们可以找几个数字，输出它每个进制的数位和。

例如：100

2:3
3:4
4:4
5:4
6:10
7:4
8:9
9:4
10:1
11:10
12:12
13:16
14:9
15:16
16:10
17:20
18:15
19:10
20:5
21:20
22:16
23:12
24:8
25:4
26:25
27:22
28:19
29:16
30:13
31:10
32:7
33:4
34:34
35:32
36:30
37:28
38:26
39:24
40:22
41:20
42:18
43:16
44:14
45:12
46:10
47:8
48:6
49:4
50:2
51:50
52:49
53:48
54:47
55:46
56:45
57:44
58:43
59:42
60:41
61:40
62:39
63:38
64:37
65:36
66:35
67:34
68:33
69:32
70:31
71:30
72:29
73:28
74:27
75:26
76:25
77:24
78:23
79:22
80:21
81:20
82:19
83:18
84:17
85:16
86:15
87:14
88:13
89:12
90:11
91:10
92:9
93:8
94:7
95:6
96:5
97:4
98:3
99:2
100:1

我们可以发现，这可以分成多段，每一段都是单调递减且有规律的。我们可以很容易地发现 $[\frac{n}{k-1},\frac{n}{k}) (k\not=0,1)$ 是一段。

因此，我们可以使用二分。（有细心的小朋友发现了，这都是等差数列，且公差为 $k-1$ ，所以其实可以用数学方法写。）

一定要注意 $s==n$ 的情况！！！

恭喜你获得基础代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int f(int b,int n){
	int ans=0;
	while(n){
		ans+=n%b;
		n/=b;
	} 
	return ans;
}
int n,s;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>s;
    if(s==n){
        cout<<n+1;
        return 0;
    }
	int las=n;
	int ans=-1;
	for(int i=2;i<=n/2;i++){
		int m=n/i;
		int L=m,R=las+1;
		while(L+1<R){
			int M=(L+R)>>1;
			if(f(M,n)>=s)L=M;
			else R=M;
		}
		if(f(L,n)==s)
			ans=L;
		las=m;
	}
	if(f(2,n)==s)
		ans=2; 
	cout<<ans;
	return 0;
}

但是这会超时。为什么呢，经过分析可知， $\sqrt{n}$ 前的每一段几乎都是单独成段，二分的时间复杂度大幅度降低，所以在 $\sqrt{n}$ 前转为暴力遍历。

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int f(int b,int n){
	int ans=0;
	while(n){
		ans+=n%b;
		n/=b;
	} 
	return ans;
}
int n,s;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>s;
	int las=n;
	int ans=-1;
	if(s==n){
		cout<<n+1;
		return 0;
	}
	for(int i=2;i*i<=n;i++){
		int m=n/i;
		int L=m,R=las+1;
		while(L+1<R){
			int M=(L+R)>>1;
			if(f(M,n)>=s)L=M;
			else R=M;
		}
		if(f(L,n)==s)
			ans=L;
		las=m;
	}
	for(int i=2;i<=las;i++){
		if(f(i,n)==s){
			ans=i;
			break;
		}
	} 
	cout<<ans;
	return 0;
}

纪念手搓绿

思路

注意到$n\leq 1\times 10^{11}$，$\sqrt{n}\leq1\times10^6$，考虑分治。对于$[1,\sqrt{n}]$的区间可以直接暴力，对于$[\sqrt{n},n]$的区间不难发现$n$在$b$进制下只有两位，令它为$\overline{xy}$，则有一下方程组：

两式相减得

直接暴力枚举$n-s$的因数，在判断是否符合进制要求，更新$ans$即可。

另外还需加一些特判。

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
	int n,s;scanf("%lld%lld",&n,&s);
	if(n==1)
	{
		if(s==1)puts("2");
		else puts("-1");
		return 0;
	}
	int ans=1ll<<60;
	if(s==n)ans=n+1;
	if(s==1)
	{
		ans=n;
		int x=sqrt(n);
		if(x*x==n)
		{
			ans=x;
			int y=sqrt(x);
			if(y*y==x)
			{
				ans=y;
			}
		}
	}
	int k=ceil(sqrt(1.0*n));
	for(int i=1;i<=sqrt(n-s);i++)if((n-s)%i==0)
	{
		int j=(n-s)/i;
		int a=(n-s)/i;
		int b=s-a;
		if(a>=0&&b>=0&&a<i+1&&b<i+1)ans=min(ans,i+1);
		a=(n-s)/j;
		b=s-a;
		if(a>=0&&b>=0&&a<j+1&&b<j+1)ans=min(ans,j+1);
	}
	for(int i=2;i<k;i++)
	{
		int x=n,cnt=0;
		while(x)
		{
			cnt+=x%i;
			x/=i;
		}
		if(cnt==s)ans=min(ans,i);
	}
	if(ans==1152921504606846976)puts("-1");
	else printf("%lld\n",ans);
	return 0;
}

没想到性质怎么办，直接打表。暴力枚举所有的 $b$，挨个算一遍。

打表后就会发现一些很显然的性质。

首先，从 $\lceil{\frac{n}{2}}\rceil$ 到 $n$，对应的 $f(b,n)$ 分别为 $\lceil\frac{n}{2}\rceil$ 到 $1$，而且看整张表没有其他更大的数了，所以 $s>\lceil\frac{n}{2}\rceil$ 时直接报告无解，但 $s=n$ 时需要特判，输出 $n+1$。

其次，从下往上看，整张表依次构成了公差为 $1,2,3\dots$ 的等差数列，每个等差数列都会在满足 $f(i,n)\ge{i-1}$ 时结束，直到 $\lfloor\sqrt{n}\rfloor$。

那这样问题就好办了，对非等差部分直接暴力跳复杂度就是 $O(\sqrt{n})$，后半部分实测差不多也是根号级别的，合起来就能过了。

重点讲一下后半部分怎么处理：

开一个 $i$ 记录跳到哪里，$d$ 记录 $f(i,n)$，$ch$ 记录当前的公差，$ans$ 记下当前的答案。

对于每一个数列，在开头时考虑 $s$ 是否被包含在那个数列中，显然至少满足下面两个条件：

1.$s\ge d$

2.$ch|(s-d)$

满足这两个条件后，显然 $s$ 要在当前基础上再往前跳 $\frac{s-d}{ch}$ 次，但这个数有可能不在这个等差数列中，所以直接计算一下此时的 $f$，相等则记录答案。

往前跳时，我们要找到最小的 $k$ 使得：

简单解一下就能得到 $k\ge\frac{i-1-d}{x+1}$，所以 $k=\lceil\frac{i-1-d}{x+1}\rceil$。

此时的 $k$ 就是这个序列的结尾，$-1$ 后就是下个序列的开头，再让 $ch\to ch+1$，$d$ 重新算一遍就完成了。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll query(ll n,ll b){
	if(b==1){
		return -1;
	}
	ll ji=0;
	while(n){
		ji+=n%b;
		n/=b;
	}
	return ji;
}
int main(){
	ll n,s;
	cin>>n>>s;
	if(n==s){
		cout<<n+1;
		return 0;
	}
	if(s>n/2+n%2){
		cout<<-1;
		return 0;
	}
	ll d=1,ch=1,i=n;
	ll ans=0;
	while(i>int(sqrt(n))){
		if(s>=d && (s-d)%ch==0 && s==query(n,i-(s-d)/ch)){
			ans=i-(s-d)/ch;
		}
		ll k=(i-d-1)/(ch+1)+((i-d-1)%(ch+1)>0);
		i-=k;
        i--;
		ch++;
		d=query(n,i);
	}
	for(i=2;i*i<=n;i++){
		d=query(n,i);
		if(d==s){
			cout<<i;
			return 0;
		}
	}
	cout<<ans;
	return 0;
}

一开始想二分，但是很快发现这个东西没有单调性。

考虑 $f(b,n) = s$，则 $n=a_kb^k+a_{k-1}b^{k-1}+...+a_0$，$s=a_k+...+a_0$。

则 $n-s=a_k(b^k-1)+...+a_1(b-1)$，易发现 $b-1 | n-s$。

那就好办了，既然 $n,s \le 10^{11}$，直接暴力枚举 $n-s$ 的所有因数验证是否符合条件，然后取最小的即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int calc(int a,int b)
{
	int ans=0;
	while(a)ans+=a%b,a/=b;
	return ans;
}
signed main()
{
	int a,b;cin>>a>>b;int sum=a-b,ans=1e12;
	if(a<b){cout<<-1;return 0;}
	if(a==b){cout<<a+1;return 0; }
	for(int i=1;i<=sqrt(sum);i++)if(sum%i==0)
	{
		if(calc(a,i+1)==b)ans=min(ans,i+1);
		if(calc(a,sum/i+1)==b)ans=min(ans,sum/i+1);
	}
	cout<<(ans==1e12?-1:ans);
	return 0;
}

zhengziye同学代码的简单注释版，要先发现答案是有规律地单调递减......

注意力惊人......

我没有注意力，所以没和他一起做出来......

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll f(ll b,ll n)
{
	ll ans=0;
	while(n)ans+=n%b,n/=b;
	return ans;
}//f函数的规律优化，不用一层层地跑
ll n,s;
int main()
{
	scanf("%lld%lld",&n,&s);
	ll las=n,ans=-1;
	if(s==n){printf("%lld\n",n+1);return 0;}
  //需要特判，如果s!=n，需要的b可以用这个代码计算，这个代码只能算比n小的答案
  //但s==n最小就是n+1，这个代码计算不出来，不加特判会输出-1，就会wa掉
	for(ll i=2;i*i<=n;i++)//log(n)跑更快...... 
	{
		ll m=n/i,l=m,r=las+1;
		while(l+1<r)
		{
			ll mid=(l+r)>>1;
			if(f(mid,n)>=s)l=mid;
			else r=mid;
		}
		//朴素二分，如果答案大了就增大b以减小f(b,n)
		//反之则减小b
		if(f(l,n)==s)ans=l;
		las=m;
	}
	for(ll i=2;i<=las;i++)if(f(i,n)==s){ans=i;break;}
	printf("%lld\n",ans);
	return 0;
}