题目描述

由于科协里最近真的很流行数字游戏，某人又命名了一种取模数，这种数字必须满足各位数字之和 mod N 为 0。现在大家又要玩游戏了，指定一个整数闭区间 [a,b]，问这个区间内有多少个取模数。

输入格式

题目有多组测试数据。每组只含三个数字 a,b,N。

输出格式

对于每个测试数据输出一行，表示各位数字和 mod N 为 0 的数的个数。

样例

Input

1 19 9

Output

2

数据范围与提示

对于全部数据，1≤a,b≤2^31−1,1≤N<100。

解题思路：

可以利用到前缀和，对当前的数进行搜索，来判断是否满足，最总得到的前缀和来相减就可以得出。

搜索时主要是对于数字所在的位置更改，数字大小，以及是都受限（是否可以继续搜索）。

代码如下

#include<bits/stdc++.h>
using namespace std;
int dp[40][300],p[40],mod;
int dfs(int pos,int num,int lim)
{
	if(!lim&&dp[pos][num]!=-1)
		return dp[pos][num];
	if(pos==0) return (num%mod)==0;
	int ans=0,n= lim==1?p[pos]:9;
	for(int i=0; i<=n; i++)
		ans+=dfs(pos-1,num+i,lim&&i==n?1:0);
	if(!lim) dp[pos][num]=ans;
	return ans;
}
int solve(int n)
{
	int k=0;
	while(n)
	{
		p[++k]=n%10;
		n/=10;
	}
	return dfs(k,0,1);
}
int main()
{
	int a,b;
	while(~scanf("%d %d %d",&a,&b,&mod)&&(a+b))
	{
		memset(dp,-1,sizeof(dp));
		printf("%d\n",solve(b)-solve(a-1));
	}
}