母関数を使うと圧倒的に速くなります。
1桁の場合母関数を次のように表します。
P1(x) = 1 + x + x4 + x9 + ... + x81
これは、各桁の平方和が0, 1, 4, 9, ..., 81になる場合が一つずつあり他は0ということを意味しています。2桁の場合は、
P2(x) = P1(x)2 = 1 + 2x + x2 + ... + x162
2xは平方和が1になる数が01と10の2つあるということです。N桁の場合はバイナリ法を使って、
PN(x) = P1(x)N
を計算します。
107で10ms、1020で80ms、10100で3.4秒でした。
