# 483. Smallest Good Base

[Link](https://leetcode.com/problems/smallest-good-base/)

**Solution**

依照等比公式: N = X^k-1/X-1, 其中X為base

N(X-1) = X^k -1 時，就表示X是一個可行的base

若X^k-1  > N(X-1) 表示X 太大, 反之則是X太小，X都不是一個可行的base

K的最大值為 log2 (10^19 ) = 60\
K的最小值為 2

```java
  public String smallestGoodBase(String n) {
        long num = Long.parseLong(n);
        long ans = 0;

        for(int k = 60; k >=2; k--){
            long min = 2;
            long max = num;
            while(max > min){
                long mid = min + (max-min)/2;
                int res = isBase(num, mid, k);
                if(res == 0){
                    ans = mid;
                    break;
                }
                else if(res > 0){
                    max = mid;
                }else{
                    min = mid+1;
                }
            }
            if(ans != 0) break;
        }
        return ""+ans;
    }
    
    public int isBase(long num, long base, int k){
        BigInteger left = (BigInteger.valueOf(base).pow(k)).subtract(BigInteger.ONE);
        BigInteger right = (BigInteger.valueOf(base).subtract(BigInteger.ONE)).multiply(BigInteger.valueOf(num));
        int cmr = left.compareTo(right);
        return cmr;
    }
```
