[AtCoder] ABC 192 D – Base n

2021年2月28日

問題

方針

\( n \) 進数で表現された \( X \) の値を \( f_n(X) \) とします。\( |X| = 1 \) のとき、\( f_n(X) = X \) であることに注意します。以降では、\( |X| \leq 2 \) のときを考えます。

自然数 \( a, b \ (a < b)\) に対して、\( f_a(X) < f_b(X) \) が成り立つので、\( f_n(X) \leq M \) を満たす最大の \(n \) を二分探索によって求めることができます。 オーバーフローに対応するために128ビット整数を使います。

コード

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

int main() {
    string X;
    ll M;
    cin >> X >> M;
    if (X.length() == 1) {
        cout << max(0ll, min(1ll, M - (X[0] - '0') + 1)) << "\n";
        return 0;
    }
    ll n = 0;
    for (char c : X) {
        if (n < c - '0') {
            n = c - '0';
        }
    }
    ll l = n;
    ll r = M + 1;
    while (r - l > 1) {
        ll m = l + (r - l) / 2;
        __int128_t d = 1;
        __int128_t x = 0;
        bool flag = false;
        for (int i = X.length() - 1; i >= 0; i--) {
            ll t = X[i] - '0';
            if (d > M || x + d * t > M) {
                flag = true;
                break;
            }
            x += d * t;
            d *= m;
        }
        if (flag) {
            r = m;
        } else {
            l = m;
        }
    }
    cout << l - n << "\n";
    return 0;
}