CodeForces 55D Beautiful numbers(数位dp)

CodeForces 55D

题目

求给定区间内的能被自己的每一非零位整除的数的个数

思路

http://www.cnblogs.com/algorithms/archive/2012/09/02/2668021.html dp[pos][mod][lcm],pos表示当前位，mod表示对2520取模，lcm表示位数的最小公倍数，离散化，取2520，lcm等处理优化的很好。

代码

#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<queue> #include<algorithm> #include<stack> using namespace std; typedef long long ll; int index[2530]; int dis[30]; ll dp[30][2520][50]; void init() { int num=0; for(int i=1; i<=2520; i++) if(2520%i==0) index[i]=num++; } 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 len,int sum,int lc ,int lim) { if(len==-1) return sum%lc==0?1:0; if(!lim&&dp[len][sum][index[lc]]!=-1) return dp[len][sum][index[lc]]; ll res=0; int u=lim?dis[len]:9; for(int i=0; i<=u; i++) { int ssum=(sum*10+i)%2520; int llc=lc; if(i) llc=lcm(lc,i); res+=dfs(len-1,ssum,llc,lim&&i==u); } if(lim) return res; else return dp[len][sum][index[lc]]=res; } ll solve(ll x) { int len=0; while(x) { dis[len++]=x%10; x/=10; } return dfs(len-1,0,1,1); } ll a,b; int main() { int T; scanf("%d",&T); init(); memset(dp,-1,sizeof(dp)); while(T--) { scanf("%I64d %I64d",&a,&b); printf("%I64d\n",solve(b)-solve(a-1)); } }