sum base r == 1111... means sum = 1+r+r^2+r^3+...+r^p

I tried two different search.

- for r = 2-10, increase p until sum>= n
- for p=2,3,4..., calculate r = sum^(1/p). then try a few numbers around r to see if the sum fits the above equation. In fact, I only tried r and got accepted by OJ.

```
public String smallestGoodBase(String n) {
long nl = 0, cur = 1;
for (int i=n.length()-1;i>=0;i--){
nl+=(n.charAt(i)-'0')*cur;
cur*=10;
}
for (long i=2;i<10;i++){
long s = 0;
cur = 1;
for (int j=0;j<nl;j++){
s+=cur;
cur*=i;
if (s == nl) return Long.toString(i);
if (s > nl) break;
}
}
long res = nl-1;
for (int i=2;i<1000;i++){
int r = (int)Math.pow(nl,1.0/i);
if (r<5) break;
if (helper(r,i,nl)&&res>r)
res = r;
}
return Long.toString(res);
}
boolean helper(int r, int i, long nl){
long res = 0;
long cur = 1;
for(int j=0;j<=i;j++){
res+=cur;
cur*=r;
if (cur>1000000000)
cur%=1000000000;
}
if (res%1000000000 == nl%1000000000) return true;
else return false;
}
```