本文主要是介绍Codeforces 55D Beautiful numbers --- 数位DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一个数能被它的所有非零数位整除，则能被它们的最小公倍数整除，而1到9的最小公倍数为2520，其中可以是最小公倍数的其实只有48个，先存下来，不然超内存。
dfs中的 n 表示之前那些位的最小公倍数
mod记录对2520取模的值，要直接拿一个很大的数对所有位的最小公倍数取模不现实，这里又用到了上次说的一个数论知识：如果两个数同余，那么对这两个数作任何相同运算，结果还是同余。
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define ll __int64
using namespace std;ll dp[20][50][2521];
int num[20],cnt,t[200];int gcd(int a,int b)
{while(a%b){int tmp=b;b=a%b;a=tmp;}return b;
}int lcm(int a,int b)
{if(b==0) return a;return a/gcd(a,b)*b;
}int sear(int x)
{int mid,bot=0,top=cnt;while(bot+1!=top){mid=bot+top>>1;if(t[mid]>x) top=mid;else bot=mid;}return bot;
}ll dfs(int n,int pos,int mod,int flag)
{if(pos==-1) return (mod%t[n])?0:1;//---if(!flag&&dp[pos][n][mod]!=-1) return dp[pos][n][mod];ll ans=0;int p,i;if(flag) p=num[pos];else p=9;for(i=0;i<=p;i++)ans+=dfs(sear(lcm(t[n],i)),pos-1,(mod*10+i)%2520,flag&&i==p);if(!flag) dp[pos][n][mod]=ans;return ans;
}ll cal(ll x)
{int l=0;while(x){num[l++]=x%10;x/=10;}return dfs(0,l-1,0,1);
}void init()
{cnt=0;for(int i=1;i<=2520;i++)if(2520%i==0) t[cnt++]=i;
}int main()
{int t;ll a,b;init();memset(dp,-1,sizeof dp);scanf("%d",&t);while(t--){scanf("%I64d%I64d",&a,&b);printf("%I64d\n",cal(b)-cal(a-1));}return 0;
}
这篇关于Codeforces 55D Beautiful numbers --- 数位DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
