### 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.

### 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