Beautiful numbers

· · 题解

CF55D Beautiful numbers

题意

一个数字 x 是美丽的，当且仅当 x\in\mathbb{Z^+} 并且对于 x 的每一个非零位上的数 y，都有 y|x。

你需要帮助他算出在区间 [l,r] \subseteq [1, 9 \times 10^{18}] 中有多少个数是美丽的。

做法

我们可以维护各个数位的 LCM。判断这个 LCM 是否整除 x 即可。

所以最暴力的数位 DP 是维护当前数，以及各个数位的 LCM。但是这比暴力还劣。

考虑维护原数对 \operatorname{lcm}(1,2,\dots,9) = 2520 取模后的值。我们断言，如果 LCM \mid (x \bmod 2520) 则一定有 LCM \mid x。

原因是，因为 2520 是 1 \sim 9 的最小公倍数，所以 x \mid 2520。所以我们直接证明 (a \bmod kx) \bmod x = a \bmod x 即可。

此时状态数是 20 \times 2 \times 2520 \times 2520，炸空间。我们发现合法的 LCM 只有 48 种（因为 2520 = 2^3 \times 3^2 \times 5 \times 7，其约数个数为 48）。进一步优化空间。