『根号分类』AT2038 桁和 / Digit Sum

$mathrmproblem$

给定$n$和$s$，求满足条件的最小$b$.

$\mathrm{S}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$

这道题的分类比较奇妙。观察到所有数据的范围比较奇妙，是$10^{11}$，很适合复杂度为根号的算法。如若复杂度不是$\sqrt{n}$，那么可以将数据范围开到$10^{18}$级别。

同时，我们发现函数$f(b,n)$的所用为：

• 求解n在b进制下各个数位的数字之和。

假设数字是两位数$xy$,那么就有$x\times b+y=n$.此时有可能存在$\sqrt{n}<b$
假设数字是三位数为$xyz$,那么就有$x\times b^2+y\times b+c=n$,此时就不存在$\sqrt{n}<b$.

因为要使$\sqrt{n}<b$，那么数字就必须是两位数。一位数的情况需要特判。

然后，我们就可以将$b$分类，当$b\le \sqrt{n}$的时候我们选择跑暴力.

剩下的就是两位数的情况，我们可以得到：$$\{\begin{array}{l}x+y=s\\ x\times b+y=n\end{array}$$

然后通过两式相减就有：$$(b?1)\times x=n?s$$

然后就有：$$b=\frac{n?s}{x}+1$$

然后我们就乱七八糟的枚举n-s的约数，判来判去即可。

代码如下：

#include <cmath>
#include <cstdio>
#include <iostream>#define int long longusing namespace std;int n, s;int f(int b,int n)
{
    if (n < b) return n;return f(b,n/b) + n % b;
}signed main(void)
{
    cin>>n>>s;if (n == s) return cout<<n+1,0; for (int i=2;i<=(int)sqrt(n);++i)if (f(i,n) == s) return cout<<i, 0; int ans = 1e18;for (int i=1;i*i<=n;++i)if ((n - s) % i == 0) {
    int b = (n - s) / i + 1;int x = i, y = s - i;if (x >= 0 && y >= 0 && b > sqrt(n) && x < b && y < b) ans = min(ans,b);}cout<<(ans == 1e18 ? -1 : ans)<<endl;return 0;
}