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

Finding numbers for which the sum of the squares of the digits is a square 题号:171 难度: 65 中英对照

For a positive integer n, let f(n) be the sum of the squares of the digits (in base 10) of n, e.g.

f(3) = 32 = 9,
f(25) = 22 + 52 = 4 + 25 = 29,
f(442) = 42 + 42 + 22 = 16 + 16 + 4 = 36

Find the last nine digits of the sum of all n, 0 < n < 1020, such that f(n) is a perfect square.

Solution

首先利用动态规划的思想求长度为$i$的数字数位平方和为$j$的数量$count[i][j]$: 更新公式为: $$count[i][j+k\times k]+=count[i-1][j]$$ 注意上式要对$10^9$取模。 其次仍然利用动态规划的思想求长度为$i$的数字数位平方和为$j$的$count[i][j]$个数字的和$sum[i][j]$: 更新公式为 $$sum[i][j+k\times k]=sum[i-1][j]+10^{i-1}\times k\times count[i-1][j]$$ 最后将所有的$sum[n][i\times i]$加起来模$10^9$即可。

Code

import java.math.BigInteger;

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

	private static final int LENGTH = 20;
	private static final int BASE = 10;
	private static final int MODULUS = 1000000000;  // Must be less than 2^31
	
	
    static public String run() {
		// Maximum possible squared digit sum (for 99...99)
		int MAX_SQR_DIGIT_SUM = (BASE - 1) * (BASE - 1) * LENGTH;
		
		// sum[n][s] is the sum of all length-n numbers with a square digit sum of s, modulo MODULUS
		long[][] sum   = new long[LENGTH + 1][MAX_SQR_DIGIT_SUM + 1];
		// count[n][s] is the count of all length-n numbers with a square digit sum of s, modulo MODULUS
		long[][] count = new long[LENGTH + 1][MAX_SQR_DIGIT_SUM + 1];
		count[0][0] = 1;
		
		for (int i = 1; i <= LENGTH; i++) {
			for (int j = 0; j < BASE; j++) {
				for (int k = 0; k + j * j <= MAX_SQR_DIGIT_SUM; k++) {
					sum[i][k + j * j] = (sum[i][k + j * j] + sum[i - 1][k] + pow(BASE, i - 1, MODULUS) * j % MODULUS * count[i - 1][k]) % MODULUS;
					count[i][k + j * j] = (count[i][k + j * j] + count[i - 1][k]) % MODULUS;
				}
			}
		}
		
		long s = 0;
		for (int i = 1; i * i <= MAX_SQR_DIGIT_SUM; i++)
			s = (s + sum[LENGTH][i * i]) % MODULUS;
		return String.format("%09d", s);
	}
    
    static public long pow(long a,int n,long mod){
    	long res=1;
    	while(n>0){
    		if((n&1)!=0) res=(res*a)%mod;
    		a=(a*a)%mod;
    		n>>=1;
    	}
    	return res;
    }
}
142989277
403ms