算法

(二分答案) $O(L \log M)$

题意是让我们求以大于等于 $d + 1$ 的数 $n$ 作为 $X$ 的进制并且 它在十进制下的值不超过 $M$ 有多少种。
首先只有 $X$ 为一位数的时候才会存在有不同的进制，得到相同值的情况，只需把它和 $M$ 比较即可。
其次，注意到 $\displaystyle v = \sum_{i = 0}^k n^i x_i$ ，$n$ 越大，相应的 $v$ 也就越大，满足单调性，故可以考虑二分 $n$。

另外还需注意，在二分的过程中，$v$ 的值可能爆 $\rm long \ long$，所以可以每次计算前先特判一下。

时间复杂度

$O(L \log M)$，其中 L 为 $X$ 的长度。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    string x;
    cin >> x;

    ll m;
    cin >> m;

    if (x.size() == 1) {
        if (stoi(x) <= m) cout << 1 << '\n';
        else cout << 0 << '\n';
        return 0;
    }

    int d = 0;
    for (char c : x) d = max(d, int(c - '0'));
    ll ac = d, wa = m + 1;
    while (wa - ac > 1) {
        ll wj = (ac + wa) / 2;
        ll v = 0;
        for (char c : x) {
            if (v > m / wj) v = m + 1;
            else v = v * wj + (c - '0');
        }
        if (v <= m) ac = wj; else wa = wj;
    }

    cout << ac - d << '\n';

    return 0;
}