合数可以有多种约数分解的形式，例如，24有7种分解方式： \begin{align*} 24&=2\times2\times2\times 3 \\ &=2\times 3\times 4 \\ &=2\times 2\times 6 \\ &=4\times 6 \\ &=3\times 8 \\ &=2\times 12 \\ &=1\times 24 \end{align*} 将一个数（在十进制下）的各位数字相加，再将和的各位数字也相加，如此反复直到得到个位数为止，最后所得的个位数就称为该数的数字根，例如467的数字根是8。

我们称一个数的给定分解的数字根和是该分解中所有约数的数字根之和，例如以上24的各个分解的数字根和分别是9、9、10、10、11、5、6。其中最大的数字根和是11。

记录$\text{mdrs}(n)$为n的最大数字根和，例如$mdrs(24)=11$。求$\sum_{n=1}^{10^6}\text{mdrs}(n)$。

本题难度:

解答

本题的题面具有误导性，事实上n不仅可以取合数，也需要取素数，当然素数只有一种分解方式。

设$n=d_0+d_1\times 10+\ldots+d_k\times 10^k$是n的十进制表示，容易看出若n不为9的倍数，则其数字根就是$n \bmod 9$，否则为其数字根为9。

用筛法找出每个数的约数表，动态规划（递推）计算 $$\text{mdrs}(n)=\max(\max_{\substack{i|n \\ i>1}}(\text{mdrs}(i)+\text{mdrs}(\frac{n}{i})),\text{mdrs}(n)),$$ 即得结果$14489159$。

target=1000000

d=[[] for i in range(target)]

for n in range(2,1000):
    for i in range(n*n,target,n):
        d[i].append(n)

mdrs=[0]*target

def s(i):
    return max(mdrs[i], i%9 if i%9>0 else 9) 
        
for n in range(2,target):
    mdrs[n]=s(n)
    if d[n]:
        mdrs[n]=max(max(s(i)+s(n/i) for i in d[n]),mdrs[n])

print sum(mdrs)