旺崽的博客

要么天赋异禀，要么天道酬勤

0%

AtCoder Beginner Contest 192 D.Base n

发表于 分类于 Valine：

题目链接

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?

Sample Input 1

1
2
22
10

Sample Output 1

1
2

Sample Input 2

1
2
999
1500

Sample Output 2

1
3

Sample Input 3

1
2
100000000000000000000000000000000000000000000000000000000000
1000000000000000000

Sample Output 3

1
1

思维+二分~
题意很简单，就是找最大的 n-进制，使得该进制下的 $X \leq M$，很容易想到二分，二分这个最大进制数即可，判断也很好判断，就是模拟 n-进制转十进制，一旦模拟的过程中大于 $M$，立即跳出即可~
这题最大的一个坑点在于 $X$ 只有一位的时候，此时任意进制下的 $X$ 都相等，所以只需要判断 $X$ 和 $M$ 的大小即可。我害怕二分模拟的过程中爆 long long，所以用 py 写的，AC 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import sys

x = input()
m = int(input())
if len(x) == 1:
    if int(x) <= m:
        print(1)
    else:
        print(0)
    sys.exit(0)
len = len(x)


def check(n):
    sum = 0
    for j in range(0, len):
        ss = 1
        for k in range(0, len - j - 1):
            ss *= n
            if ss > m:
                return 1
        sum += ss * (ord(x[j]) - ord('0'))
        if sum > m:
            return 1
    return 0


d = 0
ans = 0
for i in x:
    d = max(d, ord(i) - ord('0') + 1)

l = d
r = 10 ** 18 + 1
while l <= r:
    mid = (l + r) // 2
    if check(mid):
        r = mid - 1
    else:
        l = mid + 1
print(r - d + 1)