C++11(clang++ 3.9) 解法, 执行用时: 576ms, 内存消耗: 6908K, 提交时间: 2019-04-20 11:56:32

#include<iostream>
#include<cstdio>
#define N 165
#define ll long long
using namespace std;

int mod,tot,cnt,a[25],mark[2][25][N][N]; ll f[2][25][N][N];
ll dp(int p,int d,int s,int v){
	if (!d) return !s && !v;
	if (mark[p][d][s][v]==tot) return f[p][d][s][v];
	mark[p][d][s][v]=tot; ll t=0;
	int i,l=max(0,s-(d-1)*9),r=min((p)?9:a[d],s);
	for (i=l; i<=r; i++) t+=dp(p|(i<a[d]),d-1,s-i,(v*10+i)%mod);
	return f[p][d][s][v]=t;
}
ll solve(ll x){
	ll t=0;
	for (cnt=0; x; x/=10) a[++cnt]=x%10;
	for (mod=1; mod<=cnt*9; mod++){
		tot++; t+=dp(0,cnt,mod,0);
	}
	return t;
}
int main(){
	ll x,y; scanf("%lld%lld",&x,&y);
	printf("%lld\n",solve(y)-solve(x-1));
	return 0;
}