Processing math: 100%

Edit

【pythonでABC192を解説】D - Base n

問題概要

問題ページ

D - Base n
D - Base n

問題ページへ移動する

問題文

0 ～ 9 からなる文字列 X と、整数 M が与えられます。

X に含まれる最も大きい数字を d とします。

d+1 以上の整数 n を選んで X を n 進法表記の数とみなして得られる値のうち、M 以下であるようなものは何種類あるでしょうか？

制約

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

問題の考察

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    x = str(input().rstrip('\n'))
    m = int(input().rstrip('\n'))
    if len(x) == 1:
        if int(x) <= int(m):
            print(1)
        else:
            print(0)
    else:
        cor_v = max([int(i) for i in x])
        inc_v = 10 ** 20
        while -cor_v + inc_v > 1:
            bin_v = (cor_v + inc_v) // 2
            t = 0
            is_ok = True
            for i in range(len(x)):
                t += pow(bin_v, i) * int(x[-i-1])
                if t > m:
                    is_ok = False
                    break
            if is_ok:
                cor_v = bin_v
            else:
                inc_v = bin_v
        print(cor_v - max([int(i) for i in x]))


if __name__ == '__main__':
    solve()

-Edit
-