【Day53】483. 最小好进制

483. 最小好进制

对于给定的整数 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。

题解:

class Solution {
public:
    using LL = long long;
    string smallestGoodBase(string n) {
        LL x = stoll(n);
        for(int m = 2; m <= 60; m++){
            LL k = (LL)pow(x, 1. / m);
            if(k > 1){
                LL cur = 1;
                for(LL i = 1, base = 1; i <= m; i++){
                    base *= k;
                    cur += base;
                }
                if(cur == x) return to_string(k);
            }
        }
        return to_string(x - 1);
    }
};

   转载规则


《【Day53】483. 最小好进制》 Tyzhao 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
【Day54】1239. 串联字符串的最大长度 【Day54】1239. 串联字符串的最大长度
1239. 串联字符串的最大长度给定一个字符串数组 arr,字符串 s 是将 arr 某一子序列字符串连接所得的字符串,如果 s 中的每一个字符都只出现过一次,那么它就是一个可行解。 请返回所有可行解 s 中最长长度。 示例 1: 输入:a
2021-06-19
下一篇 
【Day52】65. 有效数字 【Day52】65. 有效数字
有效数字(按顺序)可以分成以下几个部分: 一个 小数 或者 整数 (可选)一个 ‘e’ 或 ‘E’ ,后面跟着一个 整数 小数(按顺序)可以分成以下几个部分: (可选)一个符号字符(’+’ 或 ‘-‘) 下述格式之一: 至少一位数字,
2021-06-17
  目录