题目描述
给出两个数 a,ba,b ，求出 [a,b][a,b] 中各位数字之和能整除原数的数的个数。
输入输出格式
输入格式：
一行，两个整数 aa 和 bb
输出格式：
一个整数，表示答案
输入输出样例
说明
对于所有的数据， 1 ≤ a ≤ b ≤ 10^{18}1≤a≤b≤1018
题解
数位dp
至于怎么判是否整除
我们可以考虑枚举所有位之和是多少
然后记录一下当前数模所有位之和的余数
如果为$0$说明可行
//minamoto
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
ll dp[][][],a,b;
int num[],len;
ll dfs(int pos,int p,int s1,int s2,bool flag){
if(!pos) return s1==p&&s2==;
if(s1>p||s1+pos*<p) return ;
if((~dp[pos][s1][s2])&&(!flag)) return dp[pos][s1][s2];
ll res=;int lim=flag?num[pos]:;
for(int i=;i<=lim;++i)
res+=dfs(pos-,p,s1+i,(s2*+i)%p,flag&&i==lim);
if(!flag) dp[pos][s1][s2]=res;
return res;
}
ll solve(ll x){
len=;
for(;x;x/=) num[++len]=x%;
if(!len) return 0ll;
ll res=;
for(int i=;i<=len*;++i){
memset(dp,-,sizeof(dp));
res+=dfs(len,i,,,);
}
return res;
}
int main(){
//freopen("testdata.in","r",stdin);
scanf("%lld%lld",&a,&b);
printf("%lld\n",solve(b)-solve(a-));
return ;
}