D - Base n Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

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}

入力

入力は以下の形式で標準入力から与えられる。

X
M

出力

答えを出力せよ。

入力例 1

22
10

出力例 1

2

X に含まれる最も大きい数字は 2 です。

  • X を 3 進法表記とみなして得られる値は 8 です。
  • X を 4 進法表記とみなして得られる値は 10 です。

得られる値のうち 10 以下のものはこの 2 つのみです。

入力例 2

999
1500

出力例 2

3

X に含まれる最も大きい数字は 9 です。

  • X を 10 進法表記とみなして得られる値は 999 です。
  • X を 11 進法表記とみなして得られる値は 1197 です。
  • X を 12 進法表記とみなして得られる値は 1413 です。

得られる値のうち 1500 以下のものはこの 3 つのみです。

入力例 3

100000000000000000000000000000000000000000000000000000000000
1000000000000000000

出力例 3

1

X を 2 進法表記とみなして得られる 576460752303423488 が、唯一の 1000000000000000000 以下の得られる数です。

Score : 400 points

Problem Statement

Given are a string X consisting of 0 through 9, and an integer M.

Let d be the greatest digit in X.

How many different integers not greater than M can be obtained by choosing an integer n not less than d+1 and seeing X as a base-n number?

Constraints

  • X consists of 0 through 9.
  • The length of X is between 1 and 60 (inclusive).
  • X does not begin with a 0.
  • 1 \leq M \leq 10^{18}

Input

Input is given from Standard Input in the following format:

X
M

Output

Print the answer.

Sample Input 1

22
10

Sample Output 1

2

The greatest digit in X is 2.

  • By seeing X as a base-3 number, we get 8.
  • By seeing X as a base-4 number, we get 10.

These two values are the only ones that we can obtain and are not greater than 10.

Sample Input 2

999
1500

Sample Output 2

3

The greatest digit in X is 9.

  • By seeing X as a base-10 number, we get 999.
  • By seeing X as a base-11 number, we get 1197.
  • By seeing X as a base-12 number, we get 1413.

These three values are the only ones that we can obtain and are not greater than 1500.

Sample Input 3

100000000000000000000000000000000000000000000000000000000000
1000000000000000000

Sample Output 3

1

By seeing X as a base-2 number, we get 576460752303423488, which is the only value that we can obtain and are not greater than 1000000000000000000.