题目描述

给出两个数a,b，求出[a,b]中各位数字之和能整除原数的数的个数。

输入格式

一行，两个整数a和b

输出格式

一个整数，表示答案

输入输出样例

输入 
10 19
输出 #1复制 
3

说明/提示

对于所有的数据，1 ≤ a ≤ b ≤ 10^18

解释

主函数

sss(n)-sss(m-1)         为了方便计算

SSS（）

对主函数传过来的值进行处理  然后进行   dfs

可以发现各位数之和最大只能是 9 * 18 = 162
我们可以枚举这个和 sum
然后去统计可以被 sum 整除，且数位和是 sum 的数。
我们把状态定义为 f[poo][tot][mod]
表示当前枚举到第 poo 位，目前这个数的数位和是 tot，对sum 取模是 mod.
如果满足：tot = sum 且 mod = 0，则要统计进答案。

dfs

1.    poo 记录现在填到了多少位（递减）
2.    tot      记录每位相加  %  sum  的值
3.    mod   记录现在这个数  %  sum  的值
4.    ed      记录现在填的数前面是否全部达到最大值
5.    f[][][]   其实就是一个记忆化

代码 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll m,n;
short a[100];
long long len;
long long sum;
long long f[20][400][400];
long long dfs(long long poo,long long tot,long long mod,long long ed)
{
if(tot>sum)
return 0;
if(!poo)
return mod==0&&tot==sum;
if(f[poo][tot][mod]!=-1&&!ed)
return f[poo][tot][mod];
long long g= ed?a[poo]:9;
long long ans=0;
for(long long i=0;i<=g;i++)
{
ans+=dfs(poo-1,tot+i,(mod*10+i)%sum,ed&&i==g);
}
if(!ed)
f[poo][tot][mod]=ans;// 
return ans;
}
long long sss(long long p)
{
len=0;
while(p)
{
a[++len]=p%10;
p/=10;
}
long long ans=0;
for(long long i=1;i<=9*len;i++)
{
memset(f,-1,sizeof(f));
sum=i;
ans+=dfs(len,0,0,1);
}
return ans;
}
int main()
{
cin>>m>>n;
cout<<sss(n)-sss(m-1)<<endl;
return 0;
}