寻找最小的幂，其首部由连续若干个相同数字构成

gxqcn

这个问题必须借助高精度大数算法库。 它看似乘幂，实则为高精度开方，如果需要追求高效搜索的话。 我刚才用 6# 的代码搜索 a(200)，结果如下：90832044031629032072266808763200776597377591732476977169715120443019881412500755990159501693981554567930162406118174820455381598058901681451049443406788180959583740354008958099702541401274789601262 其 200 次方的前 200 个连续数字均为 4 搜索耗时用了不到半小时，期间进行大数开方 352724 次，最大被开方数有 39392 位。 该算法效率比我最初预估的高了不少。

无心人

我觉得用浮点数计算似乎要快点 有点懒得算，呵呵 还要装mpf 另外，为什么不用个记号呢 $mIn(p)$表示$p$位数字，其中前$n$位是由$m$重复得到的

〇〇

import java.math.BigDecimal; import java.math.MathContext; public class root { public static void main(String[] args) { /* System.out.println(Math.pow(2, 1.0 / 5)); System.out.println(root(2, 5)); BigDecimal b = root(new BigDecimal(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 改进了一下 // 这个算法的收敛速度很快，可以堪称优秀了 public static double root(double num, int radix) { double result = 1.0; double pow = result; double r = pow / result; double error = pow - num; double p = r * radix; double epsilon = 1.0e-10; while (Math.abs(error) > epsilon) { result = result - error / p; pow = result; int k = 1; while (k < radix) { pow *= result; k++; } r = pow / result; error = pow - num; p = r * radix; } return result; } // BigDecimal 的 pow() 方法只能是 int 类型的，这样就不能计算 // 方根，按上述算法新增一个 public static BigDecimal root(BigDecimal num, int radix) { int precision = 6; // 增大可以提高运算精度 BigDecimal result = new BigDecimal(1); BigDecimal pow = result; BigDecimal r = pow.divide(result); BigDecimal error = pow.subtract(num); BigDecimal p = r.multiply(new BigDecimal(radix)); BigDecimal epsilon = new BigDecimal(10).pow(-precision, new MathContext(precision)); while (error.abs().compareTo(epsilon) > 0) { result = result.subtract(error.divide(p, new MathContext(precision))); pow = result; int k = 1; while (k < radix) { pow = pow.multiply(result); k++; } r = pow.divide(result); error = pow.subtract(num); p = r.multiply(new BigDecimal(radix)); } return result; } }

gxqcn

牛顿迭代法是高精度算法中经常用要用到的基本技巧之一，包括用在开方运算中。 本题若无高效的大数算法库支持，效率和精度将无法保证，很难进行下去。

〇〇

要提高效率，怎么修改算法呢

无心人

首先就不能选Java语言 呵呵

mathe

这个题目里面Java不见得会比C效率差.主要是大数运算库的效率问题

knate

3. //n 为首部由连续相同数字的长度
4. // 令 11111......111 = m (n 位相同的数字1)
5. //k 为相同的数字( 1--9)
6. // [X] 取整
8. for(k = 1;k<= 9;++k){//可能的首位相同的数字
9. for(i = 0;i<n;i++){//后面追加的0的个数
10. x = (m × 10^i) ^(1/n) ; // ^(1/n) 开n次方
11. x = [x];
12. y = ((m+1) × 10^i) ^(1/n) ;
13. y = [y];
14. if(x != y)
15. M.push_back(y);
16. }
17. }
19. return min(M);
21. //开方次数为 2 × 9 × n
22. //手上没有现成的高精度大数运算接口.没程序.
23. //使用上面的一些结果.符合.

复制代码

knate

剔除 999999 n个9的情况。

无心人

我不认为虚拟机语言的高精度计算能比C更好 除了几个底层就支持高精度计算的语言，比如Smalltalk外 Java等，必须用包装了整数运算的类再包装高精度运算 而且很多语言不能解决双精度运算问题，只能模拟双精度运算 不过java等是否语言层次支持双精度运算，俺不清楚 包括C都无法避免双精度计算问题，只能用内嵌汇编避开 虚拟机语言做双精度计算效率更低 研究过C#的il，很失望的发现，内核级的双精度计算指令没有