最小好进制

n 可以表示成由 m 个 1 组成的 k 进制数：n=(11⋯1⏟m 个)kn = (\underbrace{11 \dotsm 1}_{\text{m 个}})_k。根据数据范围，m 最大可以取到 log2nlog_2n。给定 m 和 n 后，可以快速计算出 k=⌊nm⌋k = \lfloor \sqrt[m]{n} \rfloor，然后带入检验，看计算的结果是不是 n，如果是，就返回结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  string smallestGoodBase(string n) {
    long nVal = stol(n);
    int mMax = floor(log(nVal) / log(2));
    // 枚举所有可能的 m，有 m 个 1
    for (int m = mMax; m > 1; m--) {
      // 计算一下，如果数量为 n，用 k 个 1 表示，那么是几进制数？
      // 有可能算出来是 5.5 进制数，但是这样的答案没意义，再下取整的话肯定和数量 n 对不上
      int k = pow(nVal, 1.0 / m);
      long mul = 1, sum = 1;
      // 需要检验一下答案有没有意义，把 m 个 1，k 进制表示，带入计算一下数值，是不是 n
      for (int i = 0; i < m; i++) {
        mul *= k;
        sum += mul;
      }
      if (sum == nVal) {
        return to_string(k);
      }
    }
    return to_string(nVal - 1);
  }
};