Chương trình C++ đếm số cơ số để biểu diễn số không vượt quá M

Cho chuỗi số S và số M. d là chữ số lớn nhất trong S. Đếm số nguyên cơ số n >= d+1 sao cho giá trị của S trong cơ số n không vượt quá M.

Ví dụ

Với S="999", M=1500, đầu ra 3. Cơ số 10: 999; cơ số 11: 1197; cơ số 12: 1413. Cả 3 ≤ 1500.

Giải thuật

Nếu S 1 chữ số: trả về 1 nếu giá trị ≤ M. Ngược lại, nhị phân tìm cơ số lớn nhất n sao cho giá trị ≤ M. Giá trị tính dần, nếu vượt M thì dừng. Kết quả = left - d.

Mã C++

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

int solve(string S, int M) {
    if (S.size() == 1) {
        if (stoi(S) <= M) return 1;
        else return 0;
    }
    int d = 0;
    for (char c : S) d = max(d, int(c - '0'));
    long left = d, right = M + 1;
    while (right - left > 1) {
        long mid = (left + right) / 2;
        long v = 0;
        for (char c : S) {
            if (v > M / mid) v = M + 1;
            else v = v * mid + (c - '0');
        }
        if (v <= M) left = mid;
        else right = mid;
    }
    return left - d;
}

int main() {
    string S = "999";
    int M = 1500;
    cout << solve(S, M) << endl;
}

Đầu vào / Đầu ra

Input: "999", 1500
Output: 3