题目链接：http://codeforces.com/PRoblemset/problem/55/D 题意：如果一个数字能被自己所有位上数字整除，则称这个数字为Beautiful numbers，现在问[l,r](1 ≤ l≤ r ≤ 9 *10^18)内存在多少个Beautiful numbers。 想法：依然是数位DP，对于每一位数字如果他们的最小公倍数(lcm)能够整除这个数字，那么这个数字肯定就是Beautiful numbers。可以计算出1到9的最小公倍数是2520。可以开一个三维dp[i]][j][k]，i表示第i位，j表示最高位到第i位的lcm，k表示数字对2520的模，但是k的值仍然较大，所以开数组的话，肯定会超内存的。1到9的最小公倍数只有48种，所以可以离散化处理下。 代码：
#include<stdio.h>#include<string.h>#define ll long longll dp[20][2550][50],b[2550],a[20],rev[50];void init(){ int i,num=0; for(i=1; i<=2520; i++) if(2520%i==0) b[i]=++num; memset(dp,-1,sizeof(dp));}ll lcm(ll x, ll y){ ll ans=x*y; while(x^=y^=x^=y%=x); return ans/y;}ll dfs(ll pos,ll mod,ll cm,ll last){ if(!pos) return mod%cm==0; if(!last&&dp[pos][mod][b[cm]]!=-1) return dp[pos][mod][b[cm]]; int num,i,t_mod,t_cm; ll ans=0; num=last?a[pos]:9; for(i=0; i<=num; i++) { t_mod=(mod*10+i)%2520; t_cm=i?lcm(i,cm):cm; ans+=dfs(pos-1,t_mod,t_cm,last&&i==num); } if(!last) dp[pos][mod][b[cm]]=ans; return ans;}ll cal(ll n){ int sizes=0; while(n) a[++sizes]=n%10,n/=10; return dfs(sizes,0,1,1);}int main(){ int nn; init(); scanf("%d",&nn); while(nn--) { ll l,r; scanf("%I64d%I64d",&l,&r); printf("%I64d/n",cal(r)-cal(l-1)); } return 0;}新闻热点
疑难解答
