- 最小好进制
对于给定的整数 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。
提示:
n的取值范围是 [3, 10^18]。
输入总是有效且没有前导 0。
题解:
因为考虑到大数运算,这里为了方便直接用python编写代码,现在考虑下代码,给定一个数字n,并且基底为x,那么有:
n=x ^ k+x ^ (k-1)+x ^ (k-2)+…+x ^ 1+x ^ 0
于是n=(x ^ (k+1)-1)/(x-1);
n是已经知道的,现在寻找存在的正整数x和k使得上述等式成立,于是我们想到传统的方法,一个元素遍历去对另外一个元素二分找答案,那么就无非对x从2到n-1遍历,每次遍历然后对k二分找是否存在,或者反过来对k遍历,针对每个k去二分找x这个答案。那么问题明确了,用哪种方案呢?因为n最多为1e18,遍历x的话肯定超时,所以不能这样,但是去遍历k就可以,因为k为指数,我们考虑最小的基底2,那么2的k次方大于1e18,k最多为60,然后遍历的过程中二分的时间复杂度为logn,所以最终的时间复杂度为60logn就不会超时了。
AC代码
class Solution:
def smallestGoodBase(self, n: str) -> str:
def fun(k,n):
l=int(pow(n+1,1.0/(k+1)))
if l==1:
l+=1
r=int(pow(n*(l*l)+1,1.0/(k+1)))
fin=-1
while l<=r:
mid=int((l+r)/2)
res=(mid**(k+1)-1)//(mid-1)
if res>=n:
r=mid-1
fin=mid
else:
l=mid+1
if abs((pow(fin,k+1)-1)//(fin-1)-n)<=1e-8:
return int(fin)
else:
return -1
N=int(n)
k=int(math.log(N,2))#以2为底,4的对数
ans=N-1
for i in range(k,1,-1):
#print(i)
res=fun(i,N)
if res!=-1:
ans=res
break
return str(ans)