An integer is divisible by 3 if the sum of its digits is also divisible by 3. For example, 3702 is divisible by 3 and 12 (3+7+0+2) is also divisible by 3. This property also holds for the integer 9.
In this problem, we will investigate this property for other integers.
Input
Input starts with an integer T (≤ 200), denoting the number of test cases.
Each case contains three positive integers A, B and K (1 ≤ A ≤ B < 231 and 0 < K < 10000).
Output
For each case, output the case number and the number of integers in the range [A, B] which are divisible by K and the sum of its digits is also divisible by K.
题意：给你3个数A，B，K，求A～B之间有几个数能被K整除，而且各位数之和也能被K整除。
这题类似hdu3652，方法类似，就是k看起来有点大有10000这么大，但是这么大并没什么用啊，总共不超过10位位数之和最多才90。
所以当k大于90时，直接是0了。
dp[len][mod][count]，len表示当前位数，mod表示上一位数 mod k 的余数，count表示位数之和。
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
ll dp[20][100][100];
ll a[20] , b[20];
int k;
ll dfs(int len , int mod , int flag , ll s[] , int count) {
if(len == 0) {
return mod == 0 && (count % k) == 0;
}
if(!flag && dp[len][mod][count] != -1) {
return dp[len][mod][count];
}
int t = flag ? s[len] : 9;
ll sum = 0;
for(int i = 0 ; i <= t ; i++) {
sum += dfs(len - 1 , (mod * 10 + i) % k , flag && i == t , s , count + i);
}
if(!flag)
dp[len][mod][count] = sum;
return sum;
}
ll Get(int x , int y) {
int len1 = 0 , len2 = 0;
memset(dp , -1 , sizeof(dp));
memset(a , 0 , sizeof(a));
memset(b , 0 , sizeof(b));
while(x) {
a[++len1] = x % 10;
x /= 10;
}
while(y) {
b[++len2] = y % 10;
y /= 10;
}
return dfs(len1 , 0 , 1 , a , 0) - dfs(len2 , 0 , 1 , b , 0);
}
int main()
{
int t;
cin >> t;
int ans = 0;
while(t--) {
ans++;
int A , B;
cin >> A >> B >> k;
cout << "Case " << ans << ": ";
if(k >= 90)
cout << 0 << endl;
else
cout << Get(B , A - 1) << endl;
}
return 0;
}