1.题目基本信息

1.1.题目描述

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

如果 n 的 k(k>=2) 进制数的所有数位全为1，则称 k(k>=2) 是 n 的一个 好进制 。

1.2.题目地址

https://leetcode.cn/problems/smallest-good-base/description/

2.解题方法

2.1.解题思路

数学。

记n=k^0+k^1+...+k^m。结论1：k^m<n，则m<log_k^n，又k最小为2，则m<log_2^n。结论2：按等比数列求和得，n=(1-k^(m+1))/(1-k)，则k^(m+1)=nk+1-n，则k^(m+1)<nk，即k^m<n，则kn，则n^(1/m)<k+1,；综上，k<n^(1/m)<k+1，所以k=floor(n^(1/m))。

2.2.解题步骤

第一步，通过结论1从大到小枚举m的值，第一个合法的m值对应最小的k值，即为题解。

第二步，通过m的值和结论2计算对应的k值，再验证是否是合法情况。

第三步，m==1的情况，此时n=k+1，则k=n-1。

3.解题代码

python代码

class Solution:
    def smallestGoodBase(self, n: str) -> str:
        # 思路：数学。记n=k^0+k^1+...+k^m。结论1：k^m<n，则m<log_k^n，又k最小为2，则m<log_2^n。结论2：按等比数列求和得，n=(1-k^(m+1))/(1-k)，则k^(m+1)=nk+1-n，则k^(m+1)<nk，即k^m<n，则k<n^(1/m)；二项式展开得(k+1)^m=C_m^0*(k^0)+C_m^1*(k^1)+...+C_m^m*(k^m)>n，则n^(1/m)<k+1,；综上，k<n^(1/m)<k+1，所以k=floor(n^(1/m))。
        # 第一步，通过结论1从大到小枚举m的值，第一个合法的m值对应最小的k值，即为题解
        nVal = int(n)
        mMax = int(log(nVal, 2))
        for m in range(mMax + 1, 1, -1):
            # 第二步，通过m的值和结论2计算对应的k值，再验证是否是合法情况。
            k = floor(nVal ** (1 / m))
            sum1 = 1
            mul1 = 1
            for _ in range(m):
                mul1 *= k
                sum1 += mul1
            if k >= 2 and sum1 == nVal:
                return str(k)
        # 第三步，m==1的情况，此时n=k+1，则k=n-1
        return str(nVal - 1)

c++代码

class Solution {
public:
    string smallestGoodBase(string n) {
        long nVal = stol(n);
        int mMax = floor(log(nVal) / log(2));
        for (int m = mMax; m > 1; m--) {
            int k = pow(nVal, 1.0 / m);
            long sum1 = 1, mul1 = 1;
            for (int i = 0; i < m; i++) {
                mul1 *= k;
                sum1 += mul1;
            }
            if (k > 1 && sum1 == nVal) {
                return to_string(k);
            }
        }
        return to_string(nVal - 1);
    }
};

4.执行结果