Description

Submission

class Solution {
    typedef unsigned long long ll;
public:
    string smallestGoodBase(string n) {
        ll target = stoll(n);
        ll kMax = log(target+1) / log(2) + 1;
        

        for(int k = kMax; k >= 2; --k) {
            // binary search base
            ll left = 2, right = pow(target, 1.0/(k-1));
            while(left <= right) {
                ll mid = left + (right - left) / 2;
                ll sum = 0;
                for(int i = 0; i < k; ++i) {
                    sum = sum * mid + 1;
                }

                if(sum < target) {
                    left = mid + 1;
                } else if(sum > target) {
                    right = mid - 1;
                } else {
                    return to_string(mid);
                }
            }
        }

        return to_string(target - 1);
    }
};


// 1111111111111111(k of 1's)

// traverse k, binary search base

// base^(k-1) + base^(k-2) + base^(k-3) + ... + base^0
// = (1-base^k) / (1-base) = n

// base^(k-1) + base^(k-2) + base^(k-3) + ... + base^0 = (base^(k-2) + base^(k-3) + ... + base^0) * base + 1

// 1 - base^k = n - n * base
// base^k - n * base < 0
// base^k < n * base
// base^(k-1) < n
// base < n^(1/(k-1))

// k_max: log(10^18)/log(2) < 60