problem=1068">http://www.lightoj.com/volume_showproblem.php?problem=1068

求出区间[A,B]内能被K整除且各位数字之和也能被K整除的数的个数。（1 ≤ A ≤ B < 2³¹ and 0 < K < 10000）

算是最简单的数位dp了。k在这里是10000。三维数组都开不开。可是想想会发现A,B最多有10位，各位数字之和不会超过90。那么当 k >= 90时，就不用dp，由于个位数字之和对k取余不会等于0。

#include <stdio.h>

#include <iostream>

#include <map>

#include <set>

#include <list>

#include <stack>

#include <vector>

#include <math.h>

#include <string.h>

#include <queue>

#include <string>

#include <stdlib.h>

#include <algorithm>

#define LL __int64

#define eps 1e-12

#define PI acos(-1.0)

using namespace std;

const int INF = 0x3f3f3f3f;

const int maxn = 4010;

int dp[15][92][92];

int a,b,k;

int dig[15];

int dfs(int len, int mod1, int mod2, int up)

{

	if(len == 0)

		return mod1 == 0 && mod2 == 0;

	if(!up && dp[len][mod1][mod2] != -1)

		return dp[len][mod1][mod2];

	int res = 0;

	int n = up ? dig[len] : 9;

	for(int i = 0; i <= n; i++)

	{

		int tmod1 = (mod1*10 + i)%k;

		int tmod2 = (mod2 + i)%k;

		res += dfs(len-1,tmod1,tmod2,up&&i==n);

	}

	if(!up)

		dp[len][mod1][mod2] = res;

	return res;

}

int cal(int num)

{

	int len = 0;

	while(num)

	{

		dig[++len] = num%10;

		num /= 10;

	}

	return dfs(len,0,0,1);

}

int main()

{

	int test;

	scanf("%d",&test);

	for(int item = 1; item <= test; item++)

	{

		scanf("%d %d %d",&a,&b,&k);

		if(k >= 90)

		{

			printf("Case %d: 0\n",item);

			continue;

		}

		memset(dp,-1,sizeof(dp));

		printf("Case %d: %d\n",item,cal(b) - cal(a-1));

	}

	return 0;

}