AtCoder ABC 044 D - 桁和 (ARC 060 D) (1D, 黄色, 500 点)

で場合分けする系！

• 問題へのリンク

問題概要

正の整数 が与えられる。次の条件を満たす最小の整数 （）を求めよ。(存在しない場合は -1。）

【条件】
を 進法表記したときの桁の和が である

制約

• 

考えたこと

が小さい範囲は愚直に調べればよさそうだ。 がある程度大きくなると、 を 進法で表したときの桁数が小さくなる。具体的には、 のときには、 を 進法で表すと 2 桁以内になる。

よって、次のような方針が立つ。（1 桁の場合を見落としやすいので注意。）

---

• 進法で表したときの桁数が 3 桁以上： の範囲を調べればよい
• 進法で表したときの桁数が 2 桁：後述
• 進法で表したときの桁数が 1 桁： のときに限りあり得て、 が最小である

---

2 桁の場合

進法で と表せるとすると、次のようになる。

• 
• 

これらを満たす整数 （）が存在するような を求めれば良い。

ここでは、 を固定して調べることにした。 を固定すると と求められるので、 と求められるはずである（ が の倍数でなければならない）。

まとめ

上記の場合分けによって、 の計算量で答えが求められる。

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N, S, res = -1;
    cin >> N >> S;

    // b <= √N の場合を求める
    for (long long b = 2; b * b <= N; b++) {
        long long N2 = N, sum = 0;
        while (N2) {
            sum += N2 % b;
            N2 /= b;
        }
        if (sum == S) {
            cout << b << endl;
            return 0;
        }
    }

    // b > √N のときは b 進法で 2 桁以内なので、十の位の値で場合分け
    for (long long x = 1; x * x <= N && x <= S; x++) {
        long long y = S - x;
        if ((N - y) < 0 || (N - y) % x != 0) continue;
        long long b = (N - y) / x;
        if (b <= x || b <= y || b <= 1) continue;

        if (res == -1) res = b;
        else res = min(res, b);
    }

    // 1 桁の場合
    if (N == S && res == -1) res = N + 1;
    cout << res << endl;
}