Codeforces Beta Round #51 D. Beautiful numbers 题解（数位dp+离散化） dp

题目链接题目大意就是求区间内能被所有位上的数字(!0)整除的数的个数
题目思路首先这很明显是一个数位DP
满足被所有位上的数字(!0)整除的数其实就是满足被这些位数的lcm整除
然后就是怎么处理一个数在不断变化中还要对lcm{xi}取模呢
这时候就要仔细思索其中的奥妙也是本题最重要的一点.
首先lcm{1~9}=2520;
想到每个数都是1~9中某些数字的lcm 所以他们一定能整除2520
因为若a≡b(mod m) 且d|m 则a≡b(mod d);
转化一下设b已经是对m取完模的了
于是得到若a % m=b%m 且d|m 则a % d = b%d;
因为 b=b%m 所以 b=b%m=b%d
所以 b%m%m=b%d%m
所以 b%m=b%d(km)%m
【Codeforces Beta Round #51 D. Beautiful numbers 题解（数位dp+离散化）】所以可以得到下 x%km%m<=>x%m
综上所述 x%2520%lcm{xi}==0 ; 是满足条件
而x%2520 是可以确定的和大数取模类似
mod = (mod*10+本位数字)%2520 ;
所以我们开数组的时候要有x%2520 和lcm{xi}这两项再加上位数所以数组应该这么开
dp[位数][x%2520][lcm{xi}];
但是这么开的话是这样的 dp[19][2520][2520] 1925202520 = 120657600 即使CF提供的256M的内存也会炸的不要不要的
所以得想办法优化一下
然后就想啊想终于~~
想到每个数只能是1~9的最小公倍数所以计算了下所有的lcm一共有48种可能如下:
1 2 3 4 5 6 7 8 9 10 12 14 15 18 20 21 24 28 30 35 36 40 42 45 56 60 63 70 72 84 90 105 120 126 140 168 180 210 252 280 315 360 420 504 630 840 1260 2520
共计48种
然后就可以离散化一下这样 dp[19][2520][2520]–>dp[19][2520][48]; 降低了空间复杂度就可以AC了;
其实还可以继续优化因为上面的结论所以 %2520 <=>%252的所以最后的数组可以优化到dp[19][252][48];
这样的时空复杂度均能得到下降
可以%2的原因是因为假设现在是mod，下一位是i，则为（mod*10+i）%2520=mod%252+i%2520=mod%252+i%252=(mod+i)%252
代码

#include #include #include #include #include using namespace std; typedef long long ll; const int mod=2520; int t,dig[20],fac[50],d[50][10],num[mod+5]; ll dp[20][50][mod+5]; int gcd(int a,int b){ return b==0?a:gcd(b,a%b); } int lcm(int a,int b){ return a/gcd(a,b)*b; } ll dfs(int pos,int beishu,int yu,bool limit){ if(pos==0){ return yu%fac[beishu]==0; } if(!limit&&dp[pos][beishu][yu]!=-1){ return dp[pos][beishu][yu]; } ll ans=0; int ed=limit?dig[pos]:9; for(int i=0; i<=ed; i++){ ans+=dfs(pos-1,d[beishu][i],(yu*10+i)%mod,limit&&i==ed); } if(!limit){ dp[pos][beishu][yu]=ans; } return ans; } ll work(ll x){ int cnt=0; while(x>0){ dig[++cnt]=x%10; x=x/10; } return dfs(cnt,1,0,1); } void init(){ memset(dp,-1,sizeof(dp)); int tot=0; for(int i=1; i<=mod; i++){//2520的48个因子，进行离散化 if(mod%i==0){ fac[++tot]=i; num[i]=tot; } } //预处理fac[i]和j的lcm for(int i=1; i<=tot; i++){ d[i][0]=i; for(int j=1; j<=9; j++){ d[i][j]=num[lcm(fac[i],j)]; } } } int main(){ init(); scanf("%d",&t); while(t--){ ll a,b; scanf("%I64d %I64d",&a,&b); printf("%I64d\n",work(b)-work(a-1)); } return 0; }

参考链接：https://blog.csdn.net/qq_33184171/article/details/52332586?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase