【数位DP】 CF 55D Beautiful numbers

时间:2021-09-16 20:45:46

通道:http://codeforces.com/problemset/problem/55/d

题意:[l,r]中的漂亮数。漂亮数的定义是这个数能够整除它的每一位。

思路:数位dpdp[i][j][k]:i为数字,最小共倍数为j时,这个数为k的个数。这里为什么要用到最小共倍数呢,因为一个数如果能够整除他的每一位,那么它一定能够整除他的每一位的最小共倍数。而且可以发现lcm(2~9)=2520,由于这个数根本存不下,但我们看到这里是在mod,所以2520就够了,所以空间大小为dp[19][50][2520],里面最多不超过50个最小共倍数。这里还有一个优化,我们每次计算这个数的时候都要乘以10,其实这dp[19][50][252]已经够了。

代码:https://github.com/Mithril0rd/ComplexCode/blob/master/cf55d.cpp

TAG:数位dp,[l,r]中被每位整除