[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改过题号了，这篇是以前写的

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