ABC192D - Base n

「値」が何種類かというのがポイント．ここを「$n$の種類」と読み違えると泥沼にはまる（「$X=1$の場合，無限に存在するじゃん？？？」，となる）．

上のせいで，難易度が水色なのだと予想．．．

考え方

例を見ればわかるように，$n$に関して単調増加なので，二分探索で閾値を見つければ良い．

回答例

• 条件から，$X$は必ず1以上の数を含む．
• $X$が1ケタの場合のみ例外処理が必要．

X = list(input())
M = int(input())

d = int(sorted(X)[-1])
def f(n):
  res = 0
  for i, x in enumerate(reversed(list(X))):
    res += int(x) * (n ** i)
  return res <= M
    
if not f(2):
  exit(print(0))
if len(X) == 1:
  exit(print(1))

ok = 2
ng = M + 1

while ng - ok > 1:
  mid = (ng + ok) // 2
  if f(mid):
    ok = mid
  else:
    ng = mid
    
print(max(0, ok - d))