原文链接: https://leetcode-cn.com/problems/smallest-good-base

英文原文

Given an integer n represented as a string, return the smallest good base of n.

We call k >= 2 a good base of n, if all digits of n base k are 1's.

 

Example 1:

Input: n = "13"
Output: "3"
Explanation: 13 base 3 is 111.

Example 2:

Input: n = "4681"
Output: "8"
Explanation: 4681 base 8 is 11111.

Example 3:

Input: n = "1000000000000000000"
Output: "999999999999999999"
Explanation: 1000000000000000000 base 999999999999999999 is 11.

 

Constraints:

• n is an integer in the range [3, 1018].
• n does not contain any leading zeros.

中文题目

对于给定的整数 n, 如果n的k（k>=2）进制数的所有数位全为1，则称 k（k>=2）是 n 的一个好进制。

以字符串的形式给出 n, 以字符串的形式返回 n 的最小好进制。

 

示例 1：

输入："13"
输出："3"
解释：13 的 3 进制是 111。

示例 2：

输入："4681"
输出："8"
解释：4681 的 8 进制是 11111。

示例 3：

输入："1000000000000000000"
输出："999999999999999999"
解释：1000000000000000000 的 999999999999999999 进制是 11。

 

提示：

1. n的取值范围是 [3, 10^18]。
2. 输入总是有效且没有前导 0。

 

通过代码

高赞题解

设 $n$ 可以表示成位数为 $s+1$，进制为 $k$ 的数，即 $(n)_{10}=(11\ldots 11)_k$，其中 $(a)_b$ 表示 $b$ 进制的数 $a$。那么根据任意进制转换为十进制的方法，我们有：

$$
(11\ldots 11)_k = k^s + k^{s-1} + k^{s-2} + \cdots + k + 1 = n
$$

根据上面的等式，在 $s \geq 2$ 时，显然有 $n > k^s$，并且根据二项式定理：

$$
(k+1)^s = k^s + \binom{s}{1} k^{s-1} + \binom{s}{2} k^{s-2} + \cdots + \binom{s}{s-1} k + 1
$$

可以得到 $n < (k+1)^s$，因此我们得到了解决这题的关键不等式：

$$
\forall s \geq 2, \quad k^s < n < (k+1)^s
$$

将两边同时开 $s$ 次方，得到：

$$
k < n^{1/s} < k + 1
$$

这样当 $s \geq 2$ 时，$n^{1/s}$ 的整数部分 $\lfloor n^{1/s} \rfloor$ 即为 $k$ 的值。由于题目中给定的 $n \leq 10^{18}$，因此 $s$ 的值至多为 $59$，这是因为当 $s=59$ 时，取最小的进制 $k=2$ 都有：

$$
k^{59} + k^{58} + \cdots + k + 1 = 2^{60} - 1 \approx 1.15 * 10^{18}
$$

超过了 $n$。因此我们只需要在 $[2, 59]$ 的范围内枚举 $s$ 即可。此外还有一种特殊情况 $s = 1$，此时是很简单的一种情况，进制数 $k = n-1$，在 $k$ 进制下的表示为 $11$。

下面给出我的代码和一些注释：

#define LL long long

class Solution {
public:
    string smallestGoodBase(string N) {
        // (11...11)k = k^{s} + k^{s-1} + ... + k^1 + k^0 = n
        // k^s < n < (k+1)^s
        // k < n^{1/s} < k+1
        
        LL n = stol(N);
        LL ans = n - 1;   // 将答案置为 s=1 的情况
        for (int s = 59; s >= 2; --s) {
            int k = pow(n, 1.0 / s);   // k 为 n^{1/s} 的整数部分
            if (k > 1) {    // 判断 k 是否是一个合法的进制
                LL sum = 1, mul = 1;   // 计算 (11...11)k 对应的十进制值
                for (int i = 1; i <= s; ++i) {
                    mul *= k;
                    sum += mul;
                }
                if (sum == n) {
                    ans = k;
                    break;
                }
            }
        }
        return to_string(ans);
    }
};

统计信息

通过次数	提交次数	AC比率
15963	26975	59.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言