โปรแกรม C++ นับฐานที่แทนค่าสตริงไม่เกิน M

คำอธิบายปัญหา

สมมติว่าเรามีสตริงตัวเลข S และตัวเลข M ให้ d เป็นหลักมากที่สุดใน S ต้องการหาว่ามีจำนวนเต็มที่ต่างกันกี่ค่า ที่ไม่เกิน M ที่ได้จากการเลือกฐาน n >= d+1 และนำ S มาตีความเป็นเลขฐาน n

ตัวอย่าง: S = "999"; M = 1500 ผลลัพธ์คือ 3 เพราะ:

• ฐาน 10: 999
• ฐาน 11: 1197
• ฐาน 12: 1413

ขั้นตอนการแก้ปัญหา

ถ้าความยาว S เท่ากับ 1:
    ถ้าค่าตัวเลขของ S <= M: คืนค่า 1
    มิฉะนั้น: คืนค่า 0
d := 0
สำหรับตัวอักษร c ใน S: d := max(d, c - '0')
left := d, right := M + 1
while right - left > 1:
    mid := (left + right) / 2
    v := 0
    สำหรับตัวอักษร c ใน S:
        ถ้า v > M / mid: v := M + 1
        มิฉะนั้น: v := v * mid + (c - '0')
    ถ้า v <= M: left := mid
    มิฉะนั้น: right := mid
คืนค่า left - d

ตัวอย่างโค้ด 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;
    long 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;
}

อินพุต

"999", 1500

เอาต์พุต

3