プロジェクトオイラー問171 - sinapusu2002 @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20171
Problem 171 「各桁の平方の和が平方数となる数を求める」 †
正の整数nについて, f(n)を各桁の数字(10進数)の平方の和と定義する. 例えば,

f(3) = 3^2 = 9,
f(25) = 2^2 + 5^2 = 4 + 25 = 29,
f(442) = 4^2 + 4^2 + 2^2 = 16 + 16 + 4 = 36

0 < n < 10^20について, f(n)が平方数となるようなnの和の末尾9桁を求めよ.
個数を記録する漸化式と合計を記録する漸化式の２重で楽勝です。

#include<stdio.h>
#include<string.h>
#include<iostream> 

__int64 dp[21][81*21+1],dp2[21][81*21+1];
const int MOD=100000*10000;

int main(){
	memset(dp,0,sizeof(dp));
	memset(dp2,0,sizeof(dp2));
	dp[0][0]=1;
	__int64 m=1;
	for(int i=1;i<=20;i++){
		for(int j=0;j<=9;j++){
			for(int k=j*j;k<=81*20;k++){
				dp[i][k]=(dp[i][k]+dp[i-1][k-j*j])%MOD;
				dp2[i][k]=(dp2[i][k]+dp[i-1][k-j*j]*m*j+dp2[i-1][k-j*j])%MOD;
			}
		}
		m=(m*10)%MOD;
	}
	__int64 ans=0;
	for(int i=1;i*i<=81*20;i++){
		ans=(ans+dp2[20][i*i])%MOD;
	}
	std::cout<<ans<<"\n";
}