Readme

483.Smallest-Good-Base

问题转化为等比数列 n = k^0 + k^1 +k^2 + … + k^(m-1)，对于给定的n，求最大的 m  

分析：

根据等比数列求和公式：n = (k^m-1)/(k-1)。可以看出，k越小，m越大；反之k越大，m越小。

先看m的范围：因为k最小是2，那么对应项数m最大就是 log(n)/log(2)+1；m最小是1（其实是2，无所谓了），说明m是有范围的.

如果固定m之后，再查看k的范围：因为 n > k^(m-1)，所以 k< pow(n, 1/(m-1))，也有上界。k的最小值已知是2了。说明k也是有范围的。

所以我们遍历m的值（注意从大到小遍历），然后对于固定的m，对k采用二分搜索，查找是否有(k,m)满足等比数列求和是n。

注意：

1. 给出的n是字符型。
2. 全体变量需要用长整形。
3. k的上限 pow(n,1.0/(m-1))，注意1.0
4. 二分法搜索k的时候，if (sum>N) right=k-1，否则会死循环
5. 不能使用等比公式求和公式，计算n的时候会有误差。应该采用如下的方法：

long long sum=1;
for (int i=1; i<m-1; i++)
  sum = sum*k+1;

Leetcode Link