AtCoder Regular Contest 060 D - 桁和 / Digit Sum

問題

arc060.contest.atcoder.jp

解法

本番はよくわからない解法で通したのですが, そちらも紹介したいと思います。

ある数 n に対して b を決めると, 次のような規則性があることに気付きます。

n/2+1 から n までは f(n/2+1, n) から始まって 1 ずつ f(b, n) の値が減っていきます。
n/3+1 から n/2 までは f(n/3+1, n) から始まって 2 ずつ f(b, n) の値が減っていきます。

...

n/(i+1)+1 から n/i までは f(n/(i+1), n) から始まって i ずつ f(b, n) の値が減っていきます。

この規則性通り調べることを考えると,

• までは普通に調べる
• それ以降は, 上記の規則性に従って考えると, n/i の i の候補は高々 個しかないのでそれをすべて調べる

というようにやれば良いです。

想定解もやはり で区切って場合分けをします。 までは普通に調べ, そのあとは再帰の深さが 2 にしかならないことを利用します。b > の時, n = p * b + q とおけます。一方で, s = p + q です。ゆえに, n-s = p*(b-1) となり, b の候補は n-s の約数に絞られます。これらを列挙して, 実際に解になっているかを確かめれば良いです。

想定解法っぽいコード

ll calc(ll n, ll b) {
    if (n < b) return n;
    return calc(n/b, b) + n%b;
}

ll solve(ll n, ll s) {
    for (ll i = 2; i*i <= n; i++) {
        if (calc(n, i) == s) {
            return i;
        }
    }
    vector<ll> cand;
    for (ll i = 1; i*i <= n-s; i++) {
        if ((n-s)%i == 0) cand.push_back((n-s)/i+1);
    }
    sort(cand.begin(), cand.end());
    for (ll el : cand) {
        if (calc(n, el) == s) return el;
    }
    if (n == s) {
        return n+1;
    }
    return -1;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, s;
    cin >> n >> s;
    cout << solve(n, s) << endl;
    return 0;
}

本番通したコード

ll calc(ll N, ll div) {
    if (N < div) return N;
    return N%div + calc(N/div, div);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, S;
    cin >> N >> S;
    //for (int i = 2; i <= N; i++) {
    //    cout << i << " " << calc(N, i) << endl;
    //}
    ll last = -1;
    for (ll i = 2; i*i <= N; i++) {
        last = i;
        if (calc(N, i) == S) {
            cout << i << endl;
            return 0;
        }
    }
    for (ll i = last; i > 1; i--) {
        ll start = N/i+1;
        ll last = N/(i-1);
        ll tmp = calc(N, start);
        if (tmp >= S && (tmp-S)%(i-1) == 0) {
            ll o = (tmp-S)/(i-1);
            if (start+o > last) continue;
            cout << start+o << endl;
            return 0;
        }
    }
    if (S == N) cout << N+1 << endl;
    else if (S == 1) cout << N << endl;
    else cout << -1 << endl;
    return 0;
}