C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 384K, 提交时间: 2020-06-01 09:42:01

#include<bits/stdc++.h>
using namespace std;
const int Max=12;
int n,m,l,r,f[Max][110][2];
char ch[Max];
inline int dfs(int pos,int sum,int limit)
{
	if(pos==n+1) return !sum?1:0;
	if(~f[pos][sum][limit]) return f[pos][sum][limit];
	int mx=limit?ch[pos]-'0':9,ans=0;
	for(int i=0;i<=mx;i++)
	ans+=dfs(pos+1,(sum+i)%m,limit&(i==mx));
	return f[pos][sum][limit]=ans;
}
inline int solve(int num)
{
	memset(f,-1,sizeof(f));
	sprintf(ch+1,"%d",num),n=strlen(ch+1);
	return dfs(1,0,1);
}
int main()
{
	while(cin>>l>>r>>m)
	cout<<solve(r)-solve(l-1)<<"\n";
	return 0;
}