CF55D-Beautiful numbers （数位dp）

$lcm(1,2,3,4,5,6,7,8,9)=2520$

• 若 $x$ 能被它自己的所有非零位的数字整除，即能被它们的最小公倍数整除， x≡0(modlcm({digit[i]}))x \\equiv 0(mod\\ lcm(\\{digit[i]\\}))x≡0(mod lcm({digit[i]}));
• 2520≡0(modlcm({digit[i]}))2520 \\equiv 0(mod\\ lcm(\\{digit[i]\\}))2520≡0(mod lcm({digit[i]}))
• 若 x≡0(modlcm({digit[i]}))x \\equiv 0(mod\\ lcm(\\{digit[i]\\}))x≡0(mod lcm({digit[i]}))，则 (xmod2520)≡0(modlcm({digit[i]}))(x\\ mod\\ 2520) \\equiv 0(mod\\ lcm(\\{digit[i]\\}))(x mod 2520)≡0(mod lcm({digit[i]}))

由以上可得，判断 $x$ 只需判断 $xmod2520$。

• 令 dp[i][j][k] 表示前 $i$ 位，表示的数模 $2520$ 的余数为 $j$，前 $i$ 位的最小公倍数为 $k$，这样空间为 $dp[20][2525][2525]$，明显 $MLE$；
• 考虑到 $2520$ 的约数共 $48$ 个，不是约数的最小公倍数都没有用，所以，可以将换为 $k$ 前 $i$ 位最小公倍数的元素个数，最后一维通过离散化降到 $50$，从而空间为 $dp[20][2525][50]$。

安陆市图书馆