LeetCode 483. 最小好进制

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 483. 最小好进制原题链接困难

作者：

wzc1995 , 2018-07-02 00:38:09 , 所有人可见 , 阅读 1866

题目描述

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

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

样例

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

输入："4681"
输出："8"
解释：4681 的 8 进制是 11111。

输入："1000000000000000000"
输出："999999999999999999"
解释：1000000000000000000 的 999999999999999999 进制是 11。

注意

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

算法

(枚举) $O(\log^2 n)$

假设进制为 $k$，所有数位都是 1 且共有 $t$ 位时，表示的数在十进制下为 $k^0 + k^1 + k^2 + … + k^{t-1}$。
显然 $t$ 越大，可能的 $k$ 就会越小。由于 $n$ 最大为 $10^{18}$，所以我们可以从 $1 + \lceil \log n \rceil$ 开始向下枚举 $t$。最坏情况下，$t=2$ 时必定存在 $k=n-1$ 满足条件，故枚举的下界为 3。
固定 $t$ 后，计算一个待验证的 $k = \lfloor \sqrt[t-1]{n} \rfloor$。
接下来，验证这一对 $k$ 和 $t$ 是否合法。

时间复杂度

枚举数位的时间为 $O(\log n)$，pow 函数计算的复杂度为 $O(\log n)$。
故总时间复杂度为 $O(\log^2 n)$。

C++ 代码

#define LL long long

class Solution {
public:
    string smallestGoodBase(string n) {
        LL N = stoll(n);

        for (int t = log2(N) + 1; t >= 3; t--) {
            LL k = pow(N, 1.0 / (t - 1));
            LL tot = 0;

            for (int i = 0; i < t; i++) {
                tot = tot * k + 1;
                if (tot > N)
                    break;
            }

            if (tot == N)
                return to_string(k);
        }

        return to_string(N - 1);
    }
};

8 评论

啦啦啦啦啦_8 2021-06-18 17:21

tot在计算过程中有可能越界么

wzc1995 2021-06-19 18:02

加了一个判断，防止越界。当然这个判断不是完全可靠的，但越界了除了手写高精度也没有任何办法

啦啦啦啦啦_8 2021-06-19 19:09 回复了 wzc1995 的评论

嗯嗯

风过伤痕 2020-12-01 03:06

pow好像是O(1)的？

wzc1995 2020-12-05 21:08

在特定的精度内可以看做常数，但无损精度的情况下就是 $\log n$ 的，这里为了通用性，就用了 $\log n$。

JasonSun 2019-12-23 02:49

类似实现


template <class F>
struct recursive {
  F f;
  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  const { return f(std::ref(*this), std::forward<Ts>(ts)...); }

  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  { return f(std::ref(*this), std::forward<Ts>(ts)...); }
};

template <class F> recursive(F) -> recursive<F>;
auto const rec = [](auto f){ return recursive{std::move(f)}; };


class Solution {
 public:
  string smallestGoodBase(string n) {
    using int64 = long long;
    const int64 num = std::stol(n);

    auto partial_sum_p_series = [&](int64 d, int64 x, int64 acc = 0) {
      for (int p = 0; p < d; ++p) acc = acc * x + 1;
      return acc;
    };

    auto binary_search = [&](auto lo, auto hi, auto target, auto&& f) {
      optional<decltype(lo)> result = std::nullopt;
      auto search = rec([&](auto&& search, auto lo, auto hi) -> void {
        if (auto mid = lo + (hi - lo) / 2; lo >= hi) return;
        else if (f(mid) == target) result = mid;
        else if (f(mid) > target)  search(lo, mid - 1);
        else if (f(mid) < target)  search(mid + 1, hi);
        else throw std::domain_error("unmatched case");
      });
      return (search(lo, hi), result);
    };

    for (int i = log2(num + 1); i >= 2; --i) {
      if (auto match = binary_search(int64(2), int64(pow(num, 1.0 / (i - 1)) + 1), num,
                [&](auto x) { return partial_sum_p_series(i, x); }); match)
        return std::to_string(*match);
    }
    return std::to_string(num - 1);
  }
};