Leetcode 483 - Smallest Good Base（二分+枚举）

题意

给一个数n，让我们确定一个n的进制base，使n在base的表示下是全1。即13在进制为3的表示111。

思路

我们假设x在进制为a的表示下为n个1，即$x = a^0 + a^1 + a^2 + ... + a^{n - 1}$。由于x不超过$10^{18}$，即x最大为64位。于是n最大为64。即我们可以考虑一下枚举n。

在n确定的情况下，我们可以二分一下a，如果a还没有加到$a^{n-1}$就超过x了，说明a太大。若a加到$a^{n-1}$还没有到x，说明a太小，不然刚好满足。

又由于求最小的base，于是我们的n从大往小枚举。

代码

#define LL __int128class Solution {
public:LL stringToLL(string s) {LL x = 0;for (int i = 0; i < s.size(); i++) x *= 10, x += s[i] - '0';return x;}int judge(LL x, LL a, int n) {LL s = 0, pp = 1;for (int i = 0; i < n; i++) {if (s > x) return 1;pp *= i ? a : 1;s += pp;}return s > x ? 1 : (s == x ? 0 : -1);}string LLToString(LL x) {string s = "";while (x) {s.push_back(x % 10 + '0');x /= 10;}reverse(s.begin(), s.end());return s;}string smallestGoodBase(string n) {LL x = stringToLL(n);for (int i = 64; i >= 0; i--) {LL l = 2, r = 1e18, m, ans;while (l <= r) {m = l + (r - l >> 1);if (judge(x, m, i) == 0) return LLToString(m);else if (judge(x, m, i) == 1) r = m - 1;else l = m + 1;}}return LLToString(0);}
};