[ABC044D] Digit Sum 题解

题目链接：[ABC044D] Digit Sum

题意：

对于任意非负整数 $x$ 和 $m(2\le m)$ ，定义 $f_m(x)$ 为 $x$ 在 $m$ 进制下的各位数字之和。

例如$f_{10}(87654)=8+7+6+5+4=30,~f_{100}(87654)=8+76+54=138$ 。给定两个整数 $x$ 和 $n$ 。

你需要计算是否存在某个 $m\ge 2$ 使得 $f_m(x)=n$ 。

如果存在，输出最小的满足条件的 $m$ ；如果不存在，输出 $−1$ 。

数据范围：

$1 \le x,n \le 10^{11}$

设 $x$ 化为 $m$ 进制后为 $\overline{x_1x_2\dots x_t}$

不难发现当 $t \ge 3$ 时， $m\le \sqrt{x}-\epsilon,\epsilon \in \mathbb{N}$

例如当 $t=3$ 时，设 $x$ 化为 $m$ 进制后为 $\overline{abc}$ ，则

$$x=am^2+bm+c$$

显然有 $m\le \sqrt{x}-\epsilon,\epsilon \in \mathbb{N}$

因此我们暴力枚举所有 $m\le \sqrt{x}-\epsilon,\epsilon \in \mathbb{N}$ ，对应 $t\ge 3$ 的情况

接下来 $m > \sqrt{x}-\epsilon,\epsilon \in \mathbb{N}$ 的情况，直接枚举 $m$ 肯定是不行的

注意到此时 $x$ 满足

$$x=am+b$$

因为有 $m > \sqrt{x}-\epsilon,\epsilon \in \mathbb{N}$ ，因此 $a \le \sqrt{x}-\epsilon^{\prime},\epsilon^{\prime} \in \mathbb{N}$

于是我们只要枚举这个 $a$ ，然后判断此时的 $m=\frac{x-(n-a)}{a}$ 是否合法即可

这里的合法指 $x$ 在当前 $m$ 进制下是 $am+b$

时间复杂度 $O(\sqrt{x})$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)()

int x,n,ans;
void check(int m)
{
    if(m<2) return;
    int res=0,tmp=x;
    while(tmp)
    {
        res+=tmp%m;
        tmp/=m;
    }
    if(res==n) ans=min(ans,m);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> x >> n; ans=INF;
    for(int m=2; m*m<=x; m++) check(m);
    if(x==n) ans=min(ans,n+1);
    for(int a=1; a*a<=x; a++) check((x-(n-a))/a);
    if(ans==INF) cout << "-1\n";
    else cout << ans << '\n';
    return 0;
}

---

题外话：

AtCoder改过题号了，这篇是以前写的

然后就很好笑的是题目上的题号和实际网址上的题号又是不一样的