leetcode-483-最小好进制

最小好进制

题面

leetcode题目

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

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

example

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

数据范围

• n的取值范围是 [\(3\), \(10^{18}\)]。
• 输入总是有效且没有前导 \(0\)。

题解

总体思路

这个题有点麻烦，首先对一个k进制全1的数\(n\)可以这样表示: \[ n = k^0 + k^1 + k^2 + \cdots k^m \tag{1}\] 这是一个等比数列，由等比数列求和公式有: \[ S_n = a_1\times \frac{1-q^n}{1-q} \tag{2}\] 合并\((1)\)，\((2)\)式有: \[ n = S_{m+1} = k^0 \times \frac{1-k^{m+1}}{1-k} = \frac{1-k^{m+1}}{1-k} \tag{3}\] \((3)\)式可整理为 \[ k^{m+1} = 1 - (1-k) \times n \tag{4}\] 对\((4)\)式放缩一下则为 \[ k^{m+1} = 1- (1-k) \times n < (k-1) \times n < kn \] 即为 \[ m < \frac{log_2n}{log_2k} \tag{5}\] 由\((5)\)式我们可以看出\(m\)的上界在\(n\)取最大值,\(k\)取最小值时取得，即 \[ m < \frac{log_2 10^{18}}{log_2 2} = 18 \times log_2 10 = 18 * 3.32 = 59.76 < 60 \] 在已知上届的情况下，我们甚至可以对\(m\)进行遍历，考虑\(m\)已知的情况下如何求得\(k\)。由二项式定理有: \[ (k+1)^m = C_m^{0} \times k^0 + C_m^{1} \times k^1 + C_m^2 \times k^2 + \cdots C_m^m k^m \tag{6}\] 因为\(C_a^b\geq 1\) 总是成立的，所以\((6)\)式可以放缩为: \[ (k+1)^m > k^0 + k^1 + k^2 + \cdots k^m = n \] 即: \[ n < (k+1)^m \tag{7}\] 又有: \[ n = k^0 + k^1 + k^2 + \cdots + k^m > k^m \tag{8}\] 总是成立的，所以合并\((7)\),\((8)\)式可得: \[ k^m < n < (k+1)^m \] 即: \[ k < \sqrt[m]{n} < k+1 \tag{9}\] 由\((9)\)式可知\(\sqrt[m]{n}\)总归是一个小数，并且\(k\)是这个小数的整数部分，也就是: \[ k = \lfloor \sqrt[m]{n} \rfloor \tag{10}\] 我们的工作也就变成了计算\((10)\)式的值，可以比较显然的看出\(m\)比较大时\(k\)比较小，所以如果有多组解，我们需要\(m\)最大的那一组。也就是我们从大到小遍历\(m\)，计算\(k\)，并校验\(k\)是否正确。
计算\((10)\)式的值可以采用二分法，上界为\(n\)下界为\(1\)二分\(k\)的结果，保留\(k^{mid} >= n\)时最大的那个\(mid\)即为题设。这里需要注意，当满足条件时我们取\(mid\)，当\(k^mid > n\)时，我们需要取\(mid - 1\)。判断\(k^mid\)与\(n\)的大小关系时，也可以等价为计算\(k \times log_2 mid\)与\(log_2 n\)的大小关系，这样可以节约一些时间。

代码

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <cstring>
#include <cmath>
using namespace std;
#define _DEBUG
#define LL unsigned long long

class Solution
{
public:
    string smallestGoodBase(string n)
    {
        LL nVal = stol(n);
#ifdef _DEBUG
        cout << nVal << endl;
#endif
        const LL MAXM = 60;
        for (LL i = MAXM; i >= 2; i--)
        {
            LL sq = sqrtm(nVal, i);
#ifdef _DEBUG
            cout << " sq: " << sq << endl;
#endif
            if (sq >= 2)
            {
                if (check(i, sq, nVal))
                {
                    return to_string(sq);
                }
            }
        }
        return to_string(nVal - 1);
    }

    // return \sqrt^{m}{n}
    LL sqrtm(LL n, LL m)
    {
        LL ret = 0;
        find(1, n + 1, n, m, ret);
        return ret;
    }
    void find(LL left, LL right, LL n, LL m, LL &t)
    {
        if (left >= right || right - left == 1)
        {
            return;
        }
        LL mid = (left + right) / 2;
#ifdef _DEBUG
        cout << "m: " << m << " n: " << n << " mid: " << mid << " left: " << left << " right: " << right << endl;
#endif
        double lnmid = log(mid);
        double lnn = log(n);
        if (m * lnmid < lnn)
        {
            find(mid, right, n, m, t);
        }
        else
        {
#ifdef _DEBUG
            cout << "t: " << mid << endl;
#endif
            if (m * lnmid - lnn < 1e-9)
            {
                t = mid;
            }
            else
            {
                t = mid - 1;
            }
            find(left, mid, n, m, t);
        }
    }
    bool check(LL m, LL k, LL n)
    {
#ifdef _DEBUG
        cout << "m: " << m << " n: " << n << " k:" << k << endl;
#endif
        LL ret = 1;
        LL pre = 1;
        for (LL i = 0; i < m; i++)
        {
            pre = pre * k;
            ret = ret + pre;
            if (ret == n)
            {
                return true;
            }
        }

#ifdef _DEBUG
        cout << "ret: " << ret << endl;
#endif
        return false;
    }
};

// for test
int main()
{

    Solution s;
    /*
    cout << s.smallestGoodBase("13") << endl;
    cout << s.smallestGoodBase("4681") << endl;
    cout << s.smallestGoodBase("2251799813685247") << endl;*/
    cout << s.smallestGoodBase("919818571896748567") << endl;
    return 0;
}