由于科协里最近真的很流行数字游戏。
某人又命名了一种取模数，这种数字必须满足各位数字之和 mod N 为 0。
现在大家又要玩游戏了，指定一个整数闭区间 [a.b]，问这个区间内有多少个取模数。
输入格式
输入包含多组测试数据，每组数据占一行。
每组数据包含三个整数 a,b,N。
输出格式
对于每个测试数据输出一行结果，表示区间内各位数字和 mod N 为 0 的数的个数。
数据范围
1≤a,b≤231?1,
1≤N<100
输入样例：
1 19 9
输出样例：
2
代码：
/*
1.0~x-1
我们用last表示到当前为止，前面数位上的数字之和，对此，当前第i位数字为j，前面数字之和为last，那么
后i位(包括j这一位)数字之和sum与last的关系就是(last+sum)%N == 0,那么sum%N的结果等价于(-last)%N,
所以res += f[i+1][j][(-last%N)]; (后面会提到f数组的处理)
2.x
如果j填x，那么不用枚举了，last += x，再枚举下一位即可
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 13, M = 110;
// 必须是三维 因为前面的和的模 对应了 当前位到结束的和的膜是多少
int f[N][10][M]; // f[i][j][k] 表示一共有i位，且最高位数字是j，且所有位数字和模N结果为k的数的个数
int P;
int mod(int x, int y)
{return (x % y + y) % y;
}void init()
{memset(f, 0, sizeof(f));for (int i = 0; i <= 9; i++)f[1][i][mod(i, P)]++;for (int i = 2; i < N; i++){for (int j = 0; j <= 9; j++){for (int k = 0; k < P; k++){for (int x = 0; x <= 9; x++)f[i][j][k] += f[i - 1][x][mod(k - j, P)];}}}
}
int dp(int n)
{if (!n)return 1;vector<int> num;while (n){num.push_back(n % 10);n /= 10;}int res = 0, last = 0;for (int i = num.size() - 1; i >= 0; i--){int x = num[i];for (int j = 0; j < x; j++) //左分支{res += f[i + 1][j][mod(-last, P)];}last += x; //为右分支准备if (!i && last % P == 0)res++;}return res;
}int main()
{int l, r;while (cin >> l >> r >> P){init();cout << dp(r) - dp(l - 1) << endl;}return 0;
}