SOMPO HD コンテスト(ABC192 D - Base n)【Python解答例】 - ebisukeプログラミング初心者脱出黙示録

SOMPO HD プログラミングコンテスト(ABC192)で解けなかったD問題を復習していきます。
atcoder.jp

AtCoder Beginner Contest192 D - Base n

問題文

0 ～ 9 からなる文字列 X と、整数 M が与えられます。
X に含まれる最も大きい数字を d とします。
d+1 以上の整数 n を選んで X を n 進法表記の数とみなして得られる値のうち、M 以下であるようなものは何種類あるでしょうか？

制約

・X は 0 ～ 9 のみからなる
・X の長さは 1 以上 60 以下
・X の先頭の文字は 0 ではない
・1≤M≤10^18

解答例

x = input()
m = int(input())

def Base_n_to_10(X,N): # N進数のXを10進数に変換
    out = 0
    for i in range(1,len(str(X))+1):
        out += int(X[-i])*(N**(i-1))
    return out

d = 0
for i in range(len(x)): # dを求める
    d = max(d,int(x[i]))

n = d

if len(x) == 1:  # Xが一桁の場合はコーナーケース
    if int(x) <= m:
        ans = 1
    else:
        ans = 0
else: # 二分探索
    left = n
    right = m + 1
    while right - left > 1:
        mid = (left + right) // 2
        if Base_n_to_10(x,mid) > m:
            right = mid
        else:
            left = mid
    ans = left - n
print(ans)