题目链接：
题意：一个美丽数就是可以被它的每一位的数字整除的数。
给定一个区间，求美丽数的个数。
显然这是一道数位dp，就是满足一个数能被所有位数的lcm整除即可。
一般都会设dp[len][mod][LCM]，mod表示余数，LCM表示前len位的lcm。
但是如果直接裸mod会很复杂，于是再想lcm{0,1,2,3,4,5,6,7,8,9}=2520;
而且lcm{a,b,c,d....}{a,b,c,d...表示各个位数)去重之后能被lcm{0,1,2....9}
整除。我们要求的是sum%lcm(a,b,c,d..}==0,所以只要满足
sum%lcm(0,1,2,...9}%lcm(a,b,c,d..}==0即可。于是mod就可以表示为
sum%lcm(0,1,2,...9}为多少。但是mod<=2520 && LCM<=2520这样
肯定存不下，于是要考虑如何处理LCM，毕竟很明显0~9的最大公倍数种类不会
超过48个。于是可以考虑一下离散化一下LCM，
if 2520 % num == 0 -> LCM[num]=temp++;
这样dp的三维就可以设为dp[20][2520][48];
#include#include #include #include using namespace std;typedef long long ll;const int mmax = 2520;ll n , m , dp[20][mmax][50];int temp , dig[20] , LCM[mmax + 10];ll gcd(ll a , ll b) { return b > 0 ? gcd(b , a % b) : a;}ll lcm(ll a , ll b) { return a / gcd(a , b) * b;}void init() { temp = 0; for(int i = 1 ; i <= mmax ; i++) { if(mmax % i == 0) { LCM[i] = temp++; } else { LCM[i] = 0; } }}ll dfs(int len , int count , int mod , int flag) { if(!len) { return mod % count == 0; } if(!flag && dp[len][mod][LCM[count]] != -1) { return dp[len][mod][LCM[count]]; } int t = flag ? dig[len] : 9; ll sum = 0; for(int i = 0 ; i <= t ; i++) { int Nextmod = (mod * 10 + i) % mmax; int Nextcount; if(i == 0) { Nextcount = count; } else { Nextcount = (int)lcm(count , i); } sum += dfs(len - 1 , Nextcount , Nextmod , flag && i == t); } if(!flag) dp[len][mod][LCM[count]] = sum; return sum;}ll Gets(ll x) { memset(dig , 0 , sizeof(dig)); int len = 0; if(x == 0) { dig[++len] = 0; } while(x) { dig[++len] = x % 10; x /= 10; } return dfs(len , 1 , 0 , 1);}int main() { int t; scanf("%d" , &t); init(); memset(dp , -1 , sizeof(dp)); while(t--) { scanf("%I64d%I64d" , &n , &m); printf("%I64d\n" , Gets(m) - Gets(n - 1)); } return 0;}