Project Euler 776

发表于 2022-07-27 更新于 2023-07-03 分类于 Project Euler 阅读次数： 80 本文字数： 2k 阅读时长 ≈ 2 分钟

Project Euler 776

题目

Digit Sum Division

For a positive integer $n$ , $d (n)$ is defined to be the sum of the digits of $n$ . For example, $d (12345) = 15$ .

Let $F (N) = \sum_{n = 1}^{N} \frac{n}{d (n)}$ .

You are given $F (10) = 19$ , $F (123) \approx 1.187764610390 e 3$ and $F (12345) \approx 4.855801996238 e 6$ .

Find $F (1234567890123456789)$ . Write your answer in scientific notation rounded to twelve significant digits after the decimal point. Use a lowercase e to separate the mantissa and the exponent.

解决方案

不难发现，可以将 $F$ 进行改写：

$F (N) = \sum_{n = 1}^{N} \frac{n}{d (n)} = \sum_{k = 1}^{+ \infty} \frac{1}{k} \cdot (\sum_{n \leq N, d (n) = k} n)$

改写后，相当于将 $1 \sim N$ 以内的所有数按照数位和分类好，再将它们求和即可，考虑使用动态规划的方法进行。

令 $N = 1234567890123456789$ 。考虑将 $N$ 写成一个长度为 $l$ 的十进制字符串 $N = d_{1} d_{2} d_{3} \dots d_{l}$ 。

由于 $N$ 很小，因此总数位和不会很大。

令中间状态 $c_{1} (i, j) (1 \leq i \leq l, 0 \leq j \leq 9 i)$ 分别表示如下含义：有多少个 $i$ 位有前导 0 的数，其数位和为 $j$ ，并等于由字符串 $d_{1} d_{2} \dots d_{i}$ 表示的数。令状态 $s_{1} (i, j)$ 表示 $c_{1} (i, j)$ 中的所有数之和。

不难发现，如果 $j = \sum_{k = 1}^{i} d_{k}$ ，那么 $c_{1} (i, j) = 1$ ， $s_{1} (i, j)$ 的值则为 $d_{1} d_{2} \dots d_{i}$ 这一个字符串的十进制数；否则 $c_{1} (i, j) = s_{1} (i, j) = 0$ 。

状态 $c_{1}$ 和 $s_{1}$ 的意义在于规定了答案严格在界限上的情况。而接下来定义的状态 $c_{0}, s_{0}$ 则是严格不在界限上的情况。

令状态 $c_{0} (i, j)$ 表示有多少个 $i$ 位有前导 0 的数，其数位和为 $j$ ，并严格小于由字符串 $d_{1} d_{2} \dots d_{i}$ 表示的数。令状态 $s_{0} (i, j)$ 表示 $c_{0} (i, j)$ 中的所有数之和。

那么可以先写出 $c_{0}$ 的状态转移方程：

$c_{0} (i, j) = {\begin{aligned} 1 & if i = 1 \land j < d_{1} \\ 0 & else if i = 1 \\ \sum_{k = 0}^{min (9, n)} c_{0} (i - 1, j - k) + \sum_{k = 0}^{min (9, n, d_{i} - 1)} c_{1} (i - 1, j - k) & else \end{aligned}$

方程最后一行的第一个求和项说明，如果之前的状态已经是严格小于 $d_{1} d_{2} \dots d_{i - 1}$ 的数，那么接下来无论在后面拼接哪一个数位，都是严格小于的；对于第二个求和项而言，如果之前取的值都是严格等于的，那么接下来最多只能取到 $d_{i - 1}$ 。

那么基于 $c_{0}$ 的思想，同样不难写出 $s_{0}$ 的状态转移方程：

$s_{0} (i, j) = {\begin{aligned} j & if i = 1 \land j < d_{1} \\ 0 & else if i = 1 \\ \sum_{k = 0}^{min (9, n)} (10 \cdot s_{0} (i - 1, j - k) + k \cdot c_{0} (i - 1, j - k)) + \\ \sum_{k = 0}^{min (9, n, d_{i} - 1)} (10 \cdot s_{1} (i - 1, j - k) + k \cdot c_{1} (i - 1, j - k)) & else \end{aligned}$

计算完成后，那么就可以计算 $F (N)$ ：

$F (N) = \sum_{k = 1}^{9 l} \frac{s_{0} (l, k) + s_{1} (l, k)}{k}$

代码

N = 1234567890123456789
d = list(map(int, list(str(N))))
l = len(d)
c = [[[0, 0] for _ in range((l + 1) * 9)] for _ in range(l)]
s = [[[0, 0] for _ in range((l + 1) * 9)] for _ in range(l)]
c[0][d[0]][1] = 1
s[0][d[0]][1] = d[0]
for j in range(d[0]):
    c[0][j][0] = 1
    s[0][j][0] = j
ds = d[0]
for i in range(1, l):
    ds += d[i]
    c[i][ds][1] = 1
    s[i][ds][1] = s[i - 1][ds - d[i]][1] * 10 + d[i]
    for j in range(l * 9):
        for k in range(min(j, 9) + 1):
            if k < d[i]:
                c[i][j][0] += c[i - 1][j - k][1]
                s[i][j][0] += s[i - 1][j - k][1] * 10 + c[i - 1][j - k][1] * k
            c[i][j][0] += c[i - 1][j - k][0]
            s[i][j][0] += s[i - 1][j - k][0] * 10 + c[i - 1][j - k][0] * k

ans = 0
for i in range(1, l * 9):
    ans += sum(s[-1][i]) / i
ans = "{:.12e}".format(ans).replace("e+", "e").replace("e0", "e")
print(ans)