abc044d Digit Sum

数学

题意

https://atcoder.jp/contests/abc044/tasks/arc060_b

给定两个整数 $n, s$，求最小的整数 $b(b \geq 2)$，使得 $n$ 在 $b$ 进制下的各数位和为 $s$。如果不存在这样的 $b$，输出 -1.

$1 \leq n, s \leq {10}^{11}$

思路

观察到数据范围，可以考虑根号复杂度的做法。

首先，枚举考虑 $2 \leq b \leq \sqrt n$ 的情况，每种情况暴力分解判断。

然后，对于 $b \gt \sqrt n$ 的情况，不难发现，此时 $n$ 在 $b$ 进制下最多只有两位，即 $n = d_1 \times b + d_0$。由于 $b \gt \sqrt n$，所以 $d_1 \lt \sqrt n$，且由题意 $d_0 = s - d_1$.不妨枚举 $d_1$，判断此时的 $d_0$ 与 $b$ 是否符合要求。注意特判 $d_1$ 为 $0$ 的情况，此时最小的 $b = n + 1$.

代码

long long calc(long long x, long long base) {
    long long res = 0;
    while (x) {
        res += x % base;
        x /= base;
    }
    return res;
}
void solve() {
    long long n, s;
    cin >> n >> s;
    for (long long i = 2; i <= n / i; i++) {
        if (calc(n, i) == s) {
            cout << i << '\n';
            return;
        }
    }

    long long res = -1;

    if (n == s) {
        res = n + 1;
    }
    for (long long i = 1; i <= n / i; i++) {
        long long tmp = (n - s) / i + 1;
        if ((n - s) % i == 0 && tmp >= 2 && i < tmp && s - i < tmp && s - i >= 0) {
            res = tmp;
        }
    }
    cout << res;
}