文章目录
  1. 1. 分析
  2. 2. 穷举法
    1. 2.1. Java代码
    2. 2.2. 输出

Project Euler 206,寻找特定模式(1_2_3_4_5_6_7_8_9_0)的数平方根,其中’_’是一个数字。Completed on 2013-04-25 17:35

分析

1_2_3_4_5_6_7_8_9_0格式的平方数,由于末尾是0,则平方根肯定是0结尾的,具有这个格式的最大数是:192939495969798990。由于平方根末尾是0,则这个数末尾必然是00,即这个数的格式为:1_2_3_4_5_6_7_8_900。

穷举法

经过分析,可以从具有这个格式的最大数字19293949596979899开始往下搜索,如果确定是平方数,则找到了平方根。
这个数超过了long的范围,所以要用BigInteger

Java代码

public class PE206 {
public static void main(String[] args) {
long s = System.nanoTime();
BigInteger N = new BigInteger("19293949596979899");
int max = (int) Math.sqrt(N.doubleValue()) + 1;//平方根可能的最大值
for (long i = max;; i--) {
BigInteger I = BigInteger.valueOf(i);
I = I.pow(2);
if (I.toString().matches("1.2.3.4.5.6.7.8.9")) {//平方数匹配当前模式,则找到目标
System.out.println(i * 10);
break;
}
}
System.out.println("Time consumed "
+ TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - s) + " ms");
}
}

输出

1389019170
Time consumed 68 ms
文章目录
  1. 1. 分析
  2. 2. 穷举法
    1. 2.1. Java代码
    2. 2.2. 输出