【Java】483. 最小好进制---注意大数的取值范围，使用BigInteger处理较大的数！！！

对于给定的整数 n, 如果n的k（k>=2）进制数的所有数位全为1，则称 k（k>=2）是 n 的一个好进制。

以字符串的形式给出 n, 以字符串的形式返回 n 的最小好进制。
示例 1：

输入：“13”
输出：“3”
解释：13 的 3 进制是 111。
示例 2：

输入：“4681”
输出：“8”
解释：4681 的 8 进制是 11111。
示例 3：

输入：“1000000000000000000”
输出：“999999999999999999”
解释：1000000000000000000 的 999999999999999999 进制是 11。

提示：

n的取值范围是 [3, 10^18]。
输入总是有效且没有前导 0。

思路：
k进制表示，全为1，则通过等比数列计算得到n=(k^n-1)/(k-1)
由此可以得到，n的取值范围为2<=n<=log2(n+1)
k的取值范围为2<=k<=y-1

代码：
public static String smallestGoodBase(String n) {
		 Long a=Long.parseLong(n);
		 int b=(int) (Math.log(a+1)/Math.log(2));
		 for(int i=b;i>=2;i--) {
			 long left=2,right=a;
			 while(left<=right) {
				 long mid=left + (right - left) / 2;
				 BigInteger c=BigInteger.valueOf(mid);
				 c=c.pow(i).subtract(BigInteger.ONE);
				 BigInteger d=BigInteger.valueOf(a);
				 d=d.multiply(BigInteger.valueOf(mid).subtract(BigInteger.ONE));
				 int booleans=c.compareTo(d);
				 if(booleans==0) {
					 return String.valueOf(mid);
				 }else if (booleans<0) {
					left=mid+1;
				}else {
					right=mid-1;
				}
			 }
		 }
		 return String.valueOf(a-1);
	 }

最后

以上就是痴情发箍为你收集整理的【Java】483. 最小好进制---注意大数的取值范围，使用BigInteger处理较大的数！！！的全部内容，希望文章能够帮你解决【Java】483. 最小好进制---注意大数的取值范围，使用BigInteger处理较大的数！！！所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。