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

Square root digital expansion 题号:80 难度: 20 中英对照

It is well known that if the square root of a natural number is not an integer, then it is irrational. The decimal expansion of such square roots is infinite without any repeating pattern at all.

The square root of two is 1.41421356237309504880..., and the digital sum of the first one hundred decimal digits is 475.

For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots.

Solution

对于数n,我们需要求n的平方根,有如下很有意思的规律: 先指定两个数字a和b,其中$a=5n, b=5$。 如果 $a>=b$,那么$a=a-b,b=b+10$。 否则,$a=a*100$。同时在$b$的最后一个数(始终为5)加个0。 重复上一步,$b$就会接近$n$的平方跟。

Code

import java.math.BigInteger;

public class p80 {
	
	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(){
        int j = 1;
        int res = 0;
        for(int i=1;i<=100;i++){
        	//如果平方根是整数,跳过。
            if(j*j==i){
                j++;
                continue;
            }
            res += Int_Sum(Squareroot(i,100));
        }
        return res;
    }
	
	//BigInteger 转为 int
	public static  Integer Int_Sum(BigInteger b){
        int res = 0;
        String str = b.toString();
        for(int i=0;i<str.length() ;i++){
            res += str.charAt(i) - '0';
        }
        return res;
    }
	//平方根函数
	public static  BigInteger Squareroot(int n,int digits){
        // 定义上界 
        BigInteger limit = new BigInteger("10").pow(digits+1);
        BigInteger five = new BigInteger("5");
        BigInteger ten = new BigInteger("10");
        BigInteger hunderd = new BigInteger("100");
        BigInteger a = new BigInteger(n+"").multiply(five);
        BigInteger b = five;
        while( b.compareTo(limit) < 0){
            if(a.compareTo(b) >=0){
                a = a.subtract(b);
                b = b.add(ten);
            }else{
                a = a.multiply(hunderd);
                b = b.divide(ten).multiply(hunderd).add(five);
            }
        }
        return b.divide(hunderd);
    } 

}
40886
57ms