CF55D Beautiful numbers（数位dp）

传送门

被几个数整除，等价于被他们的lcm整除。

于是想到设dp[i][j][k]表示到第i位，当前的数为j，lcm为k的数的个数。

这样空间肯定无法接受。考虑优化。

我们发现1,2,3,4,5,6,7,8,9的lcm不过是2520，我们每次把j%一下2520不会影响答案。

然后对于k这一维，直接存下当前的lcm也是不行的。

我们发现在真正由1,2,3,4,5,6,7,8,9构成的lcm（也就是2520的约数）其实很少，只有48个。

于是我们开个数组映射一下即可。

然后小心爆int。

#include<bits/stdc++.h>
#define LL long long
#define INF 2100000000
#define mod 2520
using namespace std;
LL read()
{
    LL x=0,f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    return x*f;  
}
void print(LL x)
{
    if(x<0)x=-x,putchar('-');
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
LL T;
LL cnt=0,tot=0;
LL dp[20][mod+2][50];
LL num[20];
LL a[mod+1];
LL gcd(LL a,LL b)
{
    if(b==0)return a;
    return gcd(b,a%b);
}
LL LCM(LL x,LL y)
{
    if(!y)return x;
    return x/gcd(x,y)*y;
}
LL dfs(LL x,LL shu,LL lcm,LL lim)
{
    if(!x)return (shu%lcm==0)?1:0;
    if(dp[x][shu][a[lcm]]!=-1&&!lim)return dp[x][shu][a[lcm]];
    LL maxx=lim?num[x]:9;
    LL res=0;
    for(LL i=0;i<=maxx;++i)
      res+=dfs(x-1,(shu*10+i)%mod,LCM(lcm,i),(i==maxx)&&lim);
    if(!lim)dp[x][shu][a[lcm]]=res;
    return res;
}
LL solve(LL x)
{
    tot=0;
    memset(num,0,sizeof(num));
    while(x)
    {
        num[++tot]=x%10;
        x/=10;
    }
    return dfs(tot,0,1,1);
}
int main()
{
    T=read();
    for(LL i=1;i<=mod;++i)
      if(mod%i==0)a[i]=++cnt;
    memset(dp,-1,sizeof(dp));
    while(T--)
    {
        LL l=read(),r=read();
        printf("%lld
",solve(r)-solve(l-1));
    }
}
/*
5
4 8 
12 34
56784 1356234
122 556
23 24
*/