当前位置:首页 » Project Euler » 详细页

Concealed Square 题号:206 难度: 5 中英对照

Find the unique positive integer whose square has the form 1_2_3_4_5_6_7_8_9_0,
where each “_” is a single digit.

Solution

可用**暴力破解法** 直接求解 原始答案遍历取值范围大致为$10^8$,这对于我们是不可接受的,所以通过添加一些限制条件,可将暴力破解的范围缩小很多。 针对平方数 $S=1\_2\_3\_4\_5\_6\_7\_8\_9\_0$,空格处最小取$0$最大取$9$,显然$S$的取值范围是: $$ S= [1020304050607080900,1929394959697989990] $$ 对所求答案$X$,我们可以求得$X$的取值范围为: $$ X= \sqrt {S} =[1010101010,1389026623] $$ 又观察到$S$是以$0$结尾,所以可知$X$最后一位是$0$,即$X^2$必定以$00$结尾,从而$S$的后两位为$00$。即S的范围可以确定为: $$ S= [1020304050607080900,1929394959697989900] $$ 得到新的$X$取值范围是: $$ X= \sqrt {S} =[1010101010,1389026630] $$ 由于$S$的倒数两位和$X$的末尾已经知道,把问题缩小(即去掉确认的末位),即为求满足平方数 $S=1\_2\_3\_4\_5\_6\_7\_8\_9$的值$X=[101010101,138902663]$,将结果乘以$10$即为本问题答案。$X$遍历数为: $$ |X| = |138902663-101010101|= 37892562 $$ $S$的倒数第三位是$9$,可得$X$倒数第二位是$3$或$7$,所以$X$的遍历取值可以再次缩小为: $$ X'=[10101010,13890266] $$ 其中有: $$ X=10\*X'+ 3|7 $$ 这样X的遍历范围就可以缩小到三百多万,这对于计算机来说复杂度不大,可以接受。 即最终所求的结果可表示为: $$ X=10\* (10\*X'+ 3|7) $$

Code

public class p206 {

    public static void main(String[] args) {
        long start = System.nanoTime();
        long result = run();
        long end = System.nanoTime();
        System.out.println(result);
        System.out.println((end - start) / 1000000 + "ms");
    }


    public static long run() {
        // Initialize
        // [nMin,nMax] 为X'取值的区间,所求答案为: X=10*(10*X'+ 3|7)
        long nMin = 10101010;
        long nMax = 13890266;
        long num;  //表达式中的(10*X'+ 3|7)
        long temp;
        long temp2;
        // ndigits 数组 保存 num 的平方,
        int[] ndigits = new int[17];  // Based on length of pattern

        for (long n = nMin; n <= nMax; n++) {
            num = 10 * n + 3; // X倒数第二位为3时
            temp = num;
            temp2 = temp * temp;
            //for 循环将平方结果从低位到高位存储在数组中
            for (int i = 0; i < ndigits.length; i++, temp2 /= 10)
                ndigits[i] = (int) (temp2 % 10);
            if (isConcealedSquare(ndigits)) {
                return 10 * temp;
            }

            num = 10 * n + 7; // X倒数第二位为7时
            temp = num;
            temp2 = temp * temp;
            for (int i = 0; i < ndigits.length; i++, temp2 /= 10)
                ndigits[i] = (int) (temp2 % 10);
            if (isConcealedSquare(ndigits)) {
                return 10 * num;
            }

        }
        return -1;
    }

    //判断n是否是满足条件的平方数,即 n 满足形式 1_2_3_4_5_6_7_8_9
    private static boolean isConcealedSquare(int[] n) {
        for (int i = 1; i <= 9; i++) {  // Scan for 1 to 9
            if (n[18 - i * 2] != i)
                return false;
        }
        return true;  // 符合条件
    }


}
1389019170
273ms