题意：美丽数定义：一个正数能被所有位数整除。求给出一个范围，回答这个范围内的美丽数。

思路：一个数能被所有位数整除，换句话说就是一个数能整除所有位数的LCM，所以问题就转化为一个数能否被所有位数的LCM整除。按照一般的思想，直接开三维dp[pos][num][lcm]。但是num范围很大，直接开就爆了，怎么办呢？我们可以把num%2520（即1~9的LCM）储存为mod，因为所有位数最大的LCM就是2520，所以可以mod 2520。然后你很开心的开了dp[pos][2520][2520]，然后你又爆了...

然后你可以发现虽然LCM最大是2520，但是没有一个LCM是2519这样的数字，这样就有很多空间浪费，打个表可以发现，1~9的LCM其实就48个数字，我们把这48个数字Hash一下保存，那么就缩小到了dp[pos][2520][48]。

然后你就可以A了

友谊赛被打爆了，水题都不会了

参考

代码：

#include<cstdio>

#include<map>

#include<set>

#include<vector>

#include<cstring>

#include<string>

#include<cmath>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

const int N = 50000+5;

const int INF = 0x3f3f3f3f;

using namespace std;

int dig[20];

ll dp[20][2550][50],Hash[2550];

ll Gcd(ll a,ll b){

    return b == 0? a : Gcd(b,a%b);

}

ll Lcm(ll a,ll b){

    return  a * b / Gcd(a,b);

}

ll dfs(int pos,int mod,int lcm,bool limit){

    if(pos == -1) return mod % lcm == 0? 1 : 0;

    if(!limit && dp[pos][mod][Hash[lcm]] != -1) return dp[pos][mod][Hash[lcm]];

    int top = limit? dig[pos] : 9;

    ll ret = 0;

    for(int i = 0;i <= top;i++){

        int MOD = (mod*10 + i) % 2520;

        int LCM;

        if(i) LCM = Lcm(i,lcm);

        else LCM = lcm;

        ret += dfs(pos - 1,MOD,LCM,limit && i == top);

    }

    if(!limit) dp[pos][mod][Hash[lcm]] = ret;

    return ret;

}

ll solve(ll x){

    int pos = 0;

    while(x){

        dig[pos++] = x % 10;

        x /= 10;

    }

    ll ret = dfs(pos- 1,0,1,true);

    return ret;

}

int main(){

    int T;

    ll l,r,cnt = 0;

    scanf("%d",&T);

    memset(dp,-1,sizeof(dp));

    for(int i = 1;i*i <= 2520;i++){ //hash

        if(2520 % i == 0){

            Hash[i] = cnt++;

            if(i*i != 2520){

                Hash[2520 / i] = cnt++;

            }

        }

    }

    while(T--){

        scanf("%I64d%I64d",&l,&r);

        printf("%I64d\n",solve(r) - solve(l - 1));

    }

    return 0;

}