题目的意思是给你一个数字 n,让你返回一个进制 k,使得 n 的 k 进制表示为 1111...111,即一个全 1 的表示,并且需要返回满足条件最小的 k。
朴素的思路是一个个尝试。不过就算想要暴力求解也要一点进制转换的知识。这个知识点是: 一个数字 n 的 k 进制表示可以按照 $a k^0 + b k^1 + c k^2 + ... + m k^{N-1}$ 的方式转化为十进制,其中 N 为 数字 n 的 k 进制位数。 比如十进制 3 的二进制是为 11,其位数就是 2。再比如十进制的 199,位数为 3。由于我们要求的是位全为 1 的数,因此系数全部为 1,也就是 a,b,c ...., m 全部为 1。
因此我们可从 k = 2 开始枚举,直到 n - 1,线性尝试是否可满足条件。
一进制只能有 0, 不可能有 1,故不考虑。 由于 n 进行最多 n 个数,上限是 n - 1,因此我们的枚举上限也是 n - 1。
核心伪代码:
1
n =int(n)
2
// 上面提到的 base 进制转十进制公式
3
funcsum_with(base, N):
4
returnsum(1* base ** i for i in range(N))
5
6
for k=2 to n -1:
7
ifsum_with(k, N)== n:return k
Copied!
可问题是 N 如何求出呢?
朴素的思路仍然是线性枚举。但是我们的搜索区间如何确定呢?我们知道对于一个数 n 来说,其 2 进制表示的长度一定是大于 3 进制表示的长度的。更一般而言,如果 k1 > k2,那么对于一个数字 n 的 k1 进制表示的位数一定小于 k2 进行表示的位数。 因此我们的解空间就是 [1,x] 其中 x 为 n 的二进制表示的位数。也就是说,我们可逐一枚举 N 的值 N`。
注意到需要返回的是最小的 k 进制,结合前面说的进制越小 N 越大的知识,我们应该使用从后往前倒着遍历,这样遇到满足条件的 k 可直接返回,因此在平均意义上时间复杂度更低。
1
n =int(n)
2
// 上面提到的 base 进制转十进制公式
3
funcsum_with(base, N):
4
returnsum(1* base ** i for i in range(N))
5
for N=x to 1:
6
for k=2 to n -1:
7
ifsum_with(k, N)== n:return k
Copied!
注意这里的 x 到 1 的枚举没有必要线性枚举,而是可使用二分搜索的方式进行,其依据是如果进制 k 的 N 位表示大于 n,那么 N`表示就不用看了,肯定都大,其中 N`是大于 N 的整数。