数位dp进阶题。 如果一个数能被它的所有数位整除，那么他一定可以被那些数位的\(LCM\)整除。 发现\(1-9\)的\(LCM\)是\(2520\)，所以这些数位的\(LCM\)一定是\(2520\)的约数，正确性显然。 于是就有：如果这个数\(mod\ 2520\)能被数位的\(LCM\)整除，那么这个数同样也能。 所以设计状态为：\(dp[i][j][k]\)为还剩i位没填，之前几位形成的数\(mod\ 2520 = j\)，之前所有数位\(LCM\)为\(k\)的数的个数。
转移就直接转移就行了。同时发现空间会爆炸，压缩一下\(k\)就可以了。
计算请参照我的另一篇博客：SCOI2009 windy数。
/** * @Author: Mingyu Li * @Date: 2019-03-10T10:20:16+08:00 * @Email: class11limingyu@126.com * @Filename: CF55D.cpp * @Last modified by: Mingyu Li * @Last modified time: 2019-03-10T13:12:06+08:00 */ #include <bits/stdc++.h> #define tpname typename #pragma GCC optimize("O2") #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") #define Go(i , x , y) for(register int i = x; i <= y; i++) #define God(i , y , x) for(register int i = y; i >= x; i--) typedef long long LL; typedef long double ld; typedef unsigned long long ULL; template < tpname T > void sc(T& t) { char c = getchar(); T x = 1; t = 0; while(!isdigit(c)) {if(c == '-') x = -1; c = getchar();} while(isdigit(c)) t = t * 10 + c - '0' , c = getchar();t *= x; } template < tpname T , tpname... Args > void sc(T& t , Args&... args) {sc(t); sc(args...);} template < tpname T > T mul(T x , T y , T _) { x %= _,y %= _; return ((x * y - (T)(((ld)x * y + 0.5) / _) * _) % _ + _) % _; } LL t; LL l , r , m , d[25]; LL dp[20][2525][55]; LL num[2525]; LL ca1l(LL x) { return x < 2520 ? x : x - (x / 2520) * 2520; } // dp[x][y][z]: 还剩x位 前面数%2520 = y 前面所有数lcm=z LL lcm(LL x , LL y) { if(x < y) std::swap(x,y); return !y ? x : x/std::__gcd(x,y)*y; } LL F(LL x , LL y , LL z) { if(dp[x][y][num[z]] != -1) return dp[x][y][num[z]]; if(x == 0) return dp[x][y][num[z]] = (z == 0 || (y / z) * z == y) ? 1 : 0; LL ans = 0; Go(q , 0 , 9) { ans += F(x-1 , ca1l((y * 10 + q)) , lcm(z , q)); } return dp[x][y][num[z]] = ans; } LL cal(LL x) { m = 0; while(x) { d[m++] = x%10; x /= 10; } LL ans = 0; Go(i , 1 , m-1) { Go(j , 1 , 9) ans += F(i-1 , j , j); } LL times=0 , lc=1; God(i , m-1 , 0) { Go(j , (i == m-1) ? 1 : 0 , d[i]-1) { ans += F(i ,ca1l(times * 10 + j) , lcm(lc , j)); } times = ca1l(times * 10 + d[i]); lc = lcm(lc , d[i]); } return ans; } int main() { memset(dp , -1 , sizeof(dp)); std::cin >> t; num[0] = 1; int cnt = 1; Go(i , 1 , 2520) if(2520 % i == 0) num[i] = ++cnt; while(t--) { std::cin >> l >> r; std::cout << cal(r+1) - cal(l) << std::endl; } return 0; }转载于:https://www.cnblogs.com/LiM-817/p/10887178.html
相关资源：数据结构—成绩单生成器