M보다 크지 않은 수를 나타낼 수 있는 밑수를 찾는 C++ 프로그램

숫자 문자열 S와 또 다른 숫자 M이 있다고 가정합니다. d를 S에서 가장 큰 숫자라고 가정합니다. M보다 크지 않은 여러 정수를 찾아야 합니다. n보다 작지 않은 정수 n을 선택하고 다음을 보면 찾을 수 있습니다. S를 n진법 숫자로?

따라서 입력이 S ="999"와 같으면; M =1500이면 출력은 3이 됩니다. S는 10진수로 999, 11진수로 1197, 12진수로 1413이기 때문입니다. 이 세 값만이 우리가 할 수 있는 유일한 것입니다. 획득하고 1500보다 크지 않습니다.

단계

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

if size of S is same as 1, then:
   if numeric value of S <= M, then:
      return 1
   Otherwise
      return 0
d := 0
for each character c in S, do
   d := maximum of d and (c - ASCII of '0')
left := d
right := M + 1
while right - left > 1, do:
   mid := (left + right) / 2
   v := 0
   for each character c in S, do
      if v > M / mid, then:
         v := M + 1
      Otherwise
         v := v * mid + (c - ASCII of '0')
   if v <= M, then:
      left := mid
   Otherwise
      right := mid
return left - d

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#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