题目171：寻找各个数位的平方之和也是个平方数的数字

欧拉计划

Finding numbers for which the sum of the squares of the digits is a square

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) = 3² = 9,
          f(25) = 2² + 5² = 4 + 25 = 29,
          f(442) = 4² + 4² + 2² = 16 + 16 + 4 = 36

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

题目：

对正整数 n，定义 f(n) 为它的各个数位的平方之和，例如：


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

对于 0 < n < 10²⁰， 中所有满足 f(n) 是完全平方数的 n，求这些 n 之和的最后 9 位数字。

jerryxjr1220

动态规划题目

from itertools import zip_longest as zip_l, chain, repeat
def do_fast(size = 20, m = 10**9, b = 10):
    S = [0] * (1 + (b-1)**2)
    for d in range(b): S[d * d] = d
    for k in range(1, size):
        loop = [chain(repeat(0, d * d), S) for d in range(b)]
        S = [sum(s) % m for s in zip_l(*loop, fillvalue=0)]
    s = sum([S[j**2] for j in range(int((len(S) - 1)**0.5) + 1)]) % m
    all_ones = 10**size // 9 % m
    return all_ones * s % m
print(do_fast())

142989277
[Finished in 0.2s]