这个问题必须借助高精度大数算法库。
它看似乘幂，实则为高精度开方，如果需要追求高效搜索的话。
我刚才用 6# 的代码搜索 a(200)，结果如下：90832044031629032072266808763200776597377591732476977169715120443019881412500755990159501693981554567930162406118174820455381598058901681451049443406788180959583740354008958099702541401274789601262
其 200 次方的前 200 个连续数字均为 4
搜索耗时用了不到半小时，期间进行大数开方 352724 次，最大被开方数有 39392 位。
该算法效率比我最初预估的高了不少。
我觉得用浮点数计算似乎要快点
有点懒得算，呵呵
还要装mpf
另外，为什么不用个记号呢
$mIn(p)$表示$p$位数字，其中前$n$位是由$m$重复得到的
importjava.math.BigDecimal;
importjava.math.MathContext;
public class root
{
publicstaticvoidmain(String[]args){
/*
System.out.println(Math.pow(2,1.0/5));
System.out.println(root(2,5));
BigDecimalb=root(newBigDecimal(2),5);
System.out.println(b.toString());
//可以用下面两条Java句子解决：
System.out.println(Integer.MAX_VALUE);//打印最大整数:2147483647
System.out.println(Integer.MIN_VALUE);//打印最小整数:-2147483648
//相应的浮点数：
System.out.println(Float.MAX_VALUE);
System.out.println(Float.MIN_VALUE);
//双精度：
System.out.println(Double.MAX_VALUE);
System.out.println(Double.MIN_VALUE);
for(int n=1;n<=14;n++)
label1:for(int m=1;m<=200;m++)
for(int j=1;j<9;j++)
{
if(Math.floor(Math.pow(Math.pow(10,m)*(Math.pow(10,n)-1)/9*j,1.0/n))+1
==Math.floor(Math.pow(Math.pow(10,m)*((Math.pow(10,n)-1)/9*j+1),1.0/n)))
{
System.out.print(n+":\t");
System.out.println(Math.floor(Math.pow(Math.pow(10,m)*((Math.pow(10,n)-1)/9*j+1),1.0/n)));
break label1;
}
}
*/
BigDecimal ONE=BigDecimal.ONE;
BigDecimal TEN=BigDecimal.TEN;
BigDecimal N9=TEN.subtract(ONE);
for(int n=1;n<=14;n++)
label2:for(int m=1;m<=200;m++)
for(int j=1;j<9;j++)
{
BigDecimal J=new BigDecimal(j);
BigDecimal M=root(TEN.pow(m).multiply(TEN.pow(n).add(ONE.negate()).divide(N9).multiply(J)),n).add(ONE);
BigDecimal N=root(TEN.pow(m).multiply(TEN.pow(n).add(ONE.negate()).divide(N9).multiply(J).add(ONE)),n);
if(M.toBigInteger().compareTo(N.toBigInteger())==0)
{
System.out.print(n+":\t");
System.out.println(M.toBigInteger());
break label2;
}
}
}
//算法来源：http://bbs.51js.com/thread-59522-1-197.html，9楼的回帖
//原算法使用JavaScript写的，使用Java改进了一下
//这个算法的收敛速度很快，可以堪称优秀了
publicstaticdoubleroot(doublenum,intradix){
doubleresult=1.0;
doublepow=result;
doubler=pow/result;
doubleerror=pow-num;
doublep=r*radix;
doubleepsilon=1.0e-10;
while(Math.abs(error)>epsilon){
result=result-error/p;
pow=result;
intk=1;
while(k<radix){
pow*=result;
k++;
}
r=pow/result;
error=pow-num;
p=r*radix;
}
returnresult;
}
//BigDecimal的pow()方法只能是int类型的，这样就不能计算
//方根，按上述算法新增一个
publicstaticBigDecimalroot(BigDecimalnum,intradix){
intprecision=6;//增大可以提高运算精度
BigDecimalresult=newBigDecimal(1);
BigDecimalpow=result;
BigDecimalr=pow.divide(result);
BigDecimalerror=pow.subtract(num);
BigDecimalp=r.multiply(newBigDecimal(radix));
BigDecimalepsilon=newBigDecimal(10).pow(-precision,newMathContext(precision));
while(error.abs().compareTo(epsilon)>0){
result=result.subtract(error.divide(p,newMathContext(precision)));
pow=result;
intk=1;
while(k<radix){
pow=pow.multiply(result);
k++;
}
r=pow.divide(result);
error=pow.subtract(num);
p=r.multiply(newBigDecimal(radix));
}
returnresult;
}
}
牛顿迭代法是高精度算法中经常用要用到的基本技巧之一，包括用在开方运算中。
本题若无高效的大数算法库支持，效率和精度将无法保证，很难进行下去。
要提高效率，怎么修改算法呢
首先就不能选Java语言
呵呵
这个题目里面Java不见得会比C效率差.主要是大数运算库的效率问题
//n 为首部由连续相同数字的长度
// 令 11111......111 = m (n 位相同的数字1)
//k 为相同的数字( 1--9)
// 取整
for(k = 1;k<= 9;++k){//可能的首位相同的数字
for(i = 0;i<n;i++){//后面追加的0的个数
x = (m × 10^i) ^(1/n) ;// ^(1/n)开n次方
x = ;
y = ((m+1) × 10^i) ^(1/n) ;
y = ;
if(x != y)
M.push_back(y);
}
}
returnmin(M);
//开方次数为 2 × 9× n
//手上没有现成的高精度大数运算接口.没程序.
//使用上面的一些结果.符合.
剔除 999999 n个9的情况。
我不认为虚拟机语言的高精度计算能比C更好
除了几个底层就支持高精度计算的语言，比如Smalltalk外
Java等，必须用包装了整数运算的类再包装高精度运算
而且很多语言不能解决双精度运算问题，只能模拟双精度运算
不过java等是否语言层次支持双精度运算，俺不清楚
包括C都无法避免双精度计算问题，只能用内嵌汇编避开
虚拟机语言做双精度计算效率更低
研究过C#的il，很失望的发现，内核级的双精度计算指令没有