Project Euler 159

题目

Digital root sums of factorisations

A composite number can be factored many different ways. For instance, not including multiplication by one, $24$ can be factored in $7$ distinct ways:

$\begin{array}{rl}24& =2\times 2\times 2\times 3\\ 24& =2\times 3\times 4\\ 24& =2\times 2\times 6\\ 24& =4\times 6\\ 24& =3\times 8\\ 24& =2\times 12\\ 24& =24\end{array}$

Recall that the digital root of a number, in base $10$, is found by adding together the digits of that number, and repeating that process until a number is arrived at that is less than $10$. Thus the digital root of $467$ is $8$.

We shall call a Digital Root Sum (DRS) the sum of the digital roots of the individual factors of our number.

The chart below demonstrates all of the DRS values for $24$.

Factorisation	Digital Root Sum
$2\times 2\times 2\times 3$	$9$
$2\times 3\times 4$	$9$
$2\times 2\times 6$	$10$
$4\times 6$	$10$
$3\times 8$	$11$
$2\times 12$	$5$
$24$	$6$

The maximum Digital Root Sum of $24$ is $11$.

The function $\text{mdrs}(n)$ gives the maximum Digital Root Sum of $n$. So $\text{mdrs}(24)=11$.

Find $\sum \text{mdrs}(n)$ for $1<n<1,000,000$.

解决方案

可以证明，数根的值 $r(x)=(x-1)\mathrm{\%}9+1$，也就是当 $x$ 为 $9$ 的倍数时，$r(x)=9$，否则 $r(x)=x\mathrm{\%}9$。特别的，$r(0)=0$。

由于任意一个 $k$ 位十进制数 $d=d_{k-1}...d_2{d}_1{d}_0$ 都可以写成如下形式的多项式：

$$d=\sum _{i=0}^{k=1}{d}_i{10}^i$$

因此，假设 $s(d)$ 为 $d$ 的数位和，那么有：

$$s(d)=\sum _{i=0}^{k-1}{d}_i\equiv \sum _{i=0}^{k-1}{d}_i{10}^i(\mathrm{mod}10)$$

这说明，数位和的值 $s(d)$ 和数本身的值 $d$ 关于 $9$ 同余。因此进行有限次操作后，最终得到的一位数的数字根一定和原来的数关于同余。由于正数的数位和一定大于 $0$，因此有 $r(x)=(x-1)\mathrm{\%}9+1$。

回到本题，通过类似埃氏筛法的思想，对于每个数 $n$，用一个集合 $D_n$ 存储 $n$ 的除了 $1$ 和 $n$ 以外的所有不大于 $\sqrt{n}$ 的因子。

基于动态规划的思想，可以想到，将每个数 $i$ 拆成两个非平凡因子（即不为 $1$ 或 $n$）$d$ 和 ${\displaystyle \frac{i}{d}}$ 的乘积。那么，$\text{mdrs}(d)+\text{mdrs}\left({\displaystyle \frac{i}{d}}\right)$ 有可能成为 $\text{mdrs}(i)$。

设 $f(i)=\text{mdrs(i)}(i\ge 1)$。因此，可以列出如下状态转移方程：

$$f(i)=\{\begin{array}{rlrl}& 1& & \text{if}i=1\\ & max(r(i),\underset{d\in D_i}{max}\{f(d)+f\left({\displaystyle \frac{i}{d}}\right)\})& & \text{else}\end{array}$$

最终答案为 $\sum _{i=2}^{N-1}f(i)$。

代码

# include <bits/stdc++.h>
using namespace std;
const int N=1000000;
typedef long long ll;
vector<int>g[N+4];
int f[N+4];
int fun(int x){
    return x%9?x%9:9;
}
int main(){
    for(int i=2;i<N;i++){
        for(ll j=1ll*i*i;j<N;j+=i)
            g[j].push_back(i);
    }
    int ans=0;
    for(int i=2;i<N;i++){
        f[i]=fun(i);
        for(int x:g[i])
            f[i]=max(f[i],f[x]+f[i/x]);
        ans+=f[i];
    }
    printf("%d\n",ans);
}