483

class Solution {
public:
    typedef long long ll;
    typedef unsigned long long ull;
    string smallestGoodBase(string n) {
        ull tn = stoll(n);
        ull ans;
        for(int l=62; l>=1; l--){
            if((1LL<<l) < tn)
                ans = search(tn, l);
            if(ans == 0) continue;
            return to_string(ans);
        }
        return to_string(tn-1);
    }

    ll search(ull n, ull l){
        ull left=1, right= ull(pow(1.0*n, 1.0/l)+1);
        while(left<=right){
            ull mid = (left+right)/2;
            ull prod = 1, sum=1;
            for(int d=1; d<=l && sum<=n; d++){
                prod *= mid;
                sum += prod;
            }
            if(sum == n)
                return mid;
            else if(sum < n)
                left = mid+1;
            else
                right = mid-1;
        }
        return 0;
    }
};