leetcode 483. 最小好进制

题目：483. 最小好进制 - 力扣（LeetCode）

用二进制计算位数最长是多少，然后从大到小遍历可能的位数，二分查找“进制数”即可。

class Solution {
public:
    string smallestGoodBase(string n_str) {
        uint64_t n = 0;
        for (int i = 0; i < n_str.length(); i++) {
            n = n * 10 + n_str[i] - '0';
        }
        int max = 1;
        uint64_t t = 2;
        while (t <= n / 2) {
            ++max;
            t *= 2;
        }
        ++max;
        uint64_t ret = n - 1;
        uint64_t l, r, m;
        uint64_t a;
        bool invalid;
        for (int i = max; i > 1; i--) {
            l = 2;
            r = n / i;
            while (l <= r) {
                m = (l + r) / 2;
                t = 1;
                a = 1;
                invalid = false;
                for (int j = 0; j < i; j++) {
                    if (a <= (n - t) / m) {
                        a *= m;
                        t += a;
                    } else {
                        invalid = true;
                        break;
                    }
                }
                if (!invalid && t == n) {
                    ret = m;
                    break;
                }
                if (invalid) {
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            }
            if (ret != n - 1) {
                break;
            }
        }
        
        return to_string(ret);
    }
};