题目描述
For an integer n, we call k>=2 a good base of n, if all digits of n base k are 1.
Now given a string representing n, you should return the smallest good base of n in string format.
Example 1:
Input: "13"
Output: "3"
Explanation: 13 base 3 is 111.
Example 2:
Input: "4681"
Output: "8"
Explanation: 4681 base 8 is 11111.
Example 3:
Input: "1000000000000000000"
Output: "999999999999999999"
Explanation: 1000000000000000000 base 999999999999999999 is 11.
Note:
- The range of n is [3, 10^18].
- The string representing n is always valid and will not have leading zeros.
题意:对于给定的整数 n
, 如果n
的k(k>=2)
进制数的所有数位全为1,则称k(k>=2
)是 n
的一个好进制。
以字符串的形式给出 n
, 以字符串的形式返回n
的最小好进制。
算法1
(数学不等式)
题解:如果$n$可以表示成$k$进制整数,那么我们根据$k$进制数转十进制的规则一定可以得到如下的等式:
$$
n = 1 + k + k ^2 +k^3+…+k^s
$$
我们可以发现$k$是随着$s$的增大而减小的,显然$k$有一个上界$(n - 1)$,此时$s = 1$。
我们也知道当$s > 1$时,我们根据二项式定理有:
$$
(k + 1)^s = 1 + C_s^1k+C_s^2k^2+…+C_s^sk^s>1 + k + k ^2+…+k^s = n > k^s
$$
所以我们可以得到如下不等式:
$$k^s<n<(k+1)^s$$
$$k<n^{\frac{1}{s}}<k+1$$
因此,对于任何固定的$s$,我们可以发现唯一可能合法的$k$就是$int(n^{\frac{1}{s}})$,因此我们只需要判断这个$k$值是否是关于$s$的一个正整数解即可。
我们现在知道了$s$的下界,那么$s$的上界?我们知道$k$是随着$s$的增大而减小的,那么$s$则是随着$k$减小而增大的,又$k >= 2$,所以$s$取最大值时我们仍有:
$$1+2+2^2+2^3+…+2^s <= 10^{18} $$
$$2^{s + 1} - 1\leq10^{18}$$
$$s \leq log_2(10^{18}-1)-1$$
所以$s$的上界大约是60左右的。为了找到最小的$k$,我们只需要从60开始往下枚举$s$即可,第一个合法的解就是我们要找的答案。
总的时间复杂度大约是$O(s^2) ,s <= 60$。
typedef long long LL;
string smallestGoodBase(string n) {
LL num = stol(n);
LL ans = num - 1;
for(int s = 60 ; s >= 0 ; s --)
{
LL k = pow(num,1.0/s);//潜在解
LL cur_sum = 1,temp = k;
if(k > 1)
{
for(int i = 1 ; i <= s ; i ++)
{
cur_sum += temp;
if(LONG_MAX / k > temp)//避免越界
temp = temp * k;
}
if(cur_sum == num)//判断是否是合法解
{
ans = k;
break;
}
}
}
return to_string(ans);
}