M以下の数を表すことができる塩基の数を見つけるためのC++プログラム

数値文字列Sと別の数Mがあるとします。dをSの最大の桁とします。d+1以上の整数nを選択して見ることにより、M以下の多くの異なる整数を見つける必要があります。基数としてのS-n数？

したがって、入力がS="999"のような場合。 M =1500の場合、出力は3になります。これは、Sを基数10の数値として、999を基数11の数値として、1197を基数12の数値として、1413を取得するためです。これらの3つの値は、可能な唯一の値です。取得し、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