题目链接：http://codeforces.com/problemset/problem/55/D

题意：一个美丽数就是可以被它的每一位的数字整除的数。

给定一个区间，求美丽数的个数。

显然这是一道数位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 <iostream>#include <cstring>#include <cmath>#include <cstdio>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;}

CodeForces 55D Beautiful numbers（数位dp+数学）