Codeforces 55D. Beautiful numbers

正文索引 [隐藏]

传送门:http://codeforces.com/problemset/problem/55/D

题目大意

问一个区间内,有多少个数字满足它本身能被他每一个非零数位上的数字整除。
题解

数位DP

我们考虑如果判断整除的话,我们要知道前面数字的情况,但是前面的数字非常大不好处理。
再观察,发现1~9中的质因数数量很少,所以我们只需要记录七个质因数(2,2,2,3,3,5,7)的持有情况和前面的数字对他们LCM的余数情况即可处理全部。按位数位DP即可。
然后我TLE了。。。因为多测,所以我们发现很多情况是可以不用每个测试点都算一遍的,于是优化一下,就过了。
P.S. 然后我就发现,我这不是标算,似乎又很快很快的方法欸!

代码