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
-