题目分析

很久没有看到这种数学题了，数学题是一些大厂的偏爱，如腾讯和阿里，如果有小伙伴想去大厂，可以多多练习。本题的数据量非常大，最大为1e18，因此线性复杂度以上的解法都会TLE，因此只能寻找$O(1)$或者$O(log(n))$时间复杂度的方法。

数学

我们先分析一下可能出现的位数，k进制中最小的k为2，而且进制越小位数越多。所以可以推出，位数最多有$log_{2}(n)$个。不妨设有m位
$$\therefore n = k^0 + k^1 + k^2 + … + k^{m - 1}$$
$$\because (k + 1)^{m - 1} = C_{m - 1}^{0}k^0 + C_{m - 1}^{1}k^1 + C_{m - 1}^{2}k^2 + … + C_{m - 1}^{m - 1}k^{m - 1}$$
$$\because C_{m - 1}{i} \ge 1$$
$$\therefore k^{m - 1} \le n \le (k + 1)^{m - 1}$$
$$\therefore k \le \sqrt[m - 1]{n} \le k + 1$$
因为$\sqrt[m - 1]{n}$是一个小数，所以k为其整数部分。
此时我们只要遍历位数m从$log{2}(n)$到3，对于每个位数m确定k进制，并判断$k^0 + k^1 + k^2 + … + k^{m - 1}$是否等于n。如果等于则立即停止，此时位数是最多的，所以是好进制。如果都没有找到，位数为2，k = n - 1。直接返回n - 1即可

算法的时间复杂度为$O(log^{2}(n))$，空间复杂度为$O(1)$

下面是Python语言的题解

import math
import functools


class Solution(object):
    def smallestGoodBase(self, n):
        """
        :type n: str
        :rtype: str
        """
        n = int(n)
        bit = int(math.log2(n)) + 1
        for m in range(bit, 2, -1):
            k = int(n ** (1 / (m - 1)))
            if n == functools.reduce(lambda x, _: x * k + 1, [1] * m):
                return str(k)
        return str(n - 1)

下面是Kotlin语言的题解

import kotlin.math.log2


class Solution {
    fun smallestGoodBase(n: String): String {
        val nn = n.toLong()
        val bit = log2(nn.toDouble()).toInt() + 1
        for (m in bit downTo 3) {
            val k = (Math.pow(nn.toDouble(), 1 / (m - 1).toDouble())).toInt()
            if (nn == LongArray(m) {1}.reduce() {x, _ -> x * k + 1}) { return k.toString() }
        }
        return (nn - 1).toString()
    }
}

对比Python和Kotlin两种语言，Python语言更加简洁，不需要将数据类型toLong, toDouble互相转换。在Python中reduce在functools包中，而在Kotlin中，reduce是数组的一个成员方法，在使用时通常都使用lambda表达式。

刷题总结

本题类似于高中数列的证明题，难度不算大，题解也能很容易的理解，使用简单的放缩法即可，但是能否想到放缩是本题的难点。