【CF55D】Beautiful numbers（动态规划）

题面

洛谷

CF

题解

数位\(dp\)

如果当前数能够被它所有数位整除，意味着它能够被所有数位的\(lcm\)整除。

所以\(dp\)的时候前面所有数的\(lcm\)要压进\(dp\)值中。

又因为\(lcm\)的余数也是有意义的，但是又不能暴力记，

所以记录一下\([1,9]\)所有数的\(lcm\)也就是\(2520\)就好了。

但是数组太大，实际上，有意义的\(lcm\)个数只有不到\(50\)个，重新编号就可以压缩状态了。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
inline ll read()
{
    ll x=0,t=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
int lcm[3000],tot,p[50];
ll f[20][50][2520];
int W[20],top;
int LCM(int a,int b){if(b==0)return a;return a/__gcd(a,b)*b;}
ll dfs(int x,int Lcm,int r,int t)
{
if(!x)return r%p[Lcm]==0;
if(f[x][Lcm][r]!=-1&&!t)return f[x][Lcm][r];
int up=t?W[x]:9;ll ret=0;
for(int i=0;i<=up;++i)
ret+=dfs(x-1,lcm[LCM(p[Lcm],i)],(r*10+i)%2520,t&(i==W[x]));
if(!t)f[x][Lcm][r]=ret;
return ret;
}
ll Solve(ll x)
{
top=0;
while(x)W[++top]=x%10,x/=10;
return dfs(top,1,0,1);
}
int main()
{
for(int i=0;i<(1<<9);++i)
{
int sum=1;
for(int j=0;j<9;++j)
if(i&(1<<j))sum=LCM(sum,j+1);
lcm[sum]=1;
}
for(int i=1;i<=2520;++i)if(lcm[i])lcm[i]=++tot,p[tot]=i;
memset(f,-1,sizeof(f));int T=read();
while(T--)
{
ll l=read(),r=read();
cout<<Solve(r)-Solve(l-1)<<endl;
}
return 0;
}