套路来讲定义f[i][j][k]
表示 i位数，最高位为j，mod n为k的满足条件的数的个数

这里提供一种两维状态的方法
去掉第二维，也就是不需要最高位是几这一维
初始化时枚举 当前这一位是谁 和 之前所有位的和，转移到算上这一位的和 % n 即可

计算时枚举第i位是j的话，答案只需累加上 （i-1位的和 + j） mod n == 0的方案数即可
在mod n 意义下这样的数只有一个，可直接算出

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int N = 10;

int f[N][N * N],n;

void init()
{
    memset(f,0,sizeof f);
    f[0][0] = 1;

    for(int i = 1;i < N;i ++)
        for(int j = 0;j <= 9;j ++)
            for(int k = 0;k <= n;k ++)
                f[i][(j + k) % n] += f[i - 1][k];
}

int dp(int x)
{
    if(!x)return 1;

    vector<int> num;
    while(x)num.push_back(x % 10),x /= 10;

    int res = 0,last = 0;
    for(int i = num.size() - 1;i >= 0;i --)
    {
        for(int j = 0;j < num[i];j ++)
            res += f[i][(10 * n - last - j) % n];

        last = (last + num[i]) % n;

        if(!last)res++;
    }

    return res;
}

int main()
{
    int l,r;
    while(cin >> l >> r >> n)
    {
        init();

        cout << dp(r) - dp(l - 1) << endl;        
    }
}