二刷提高课，题解目录在这里— 提高课的题解目录

//数位DP其实框架都差不多，所以和前面差不多，但是这里不用特意判断前导零
//还有N是不同的所以我们每次都要初始化一下

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N=15;
int f[N][10][110];
int p;
int l,r;
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][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 w=0;w<=9;w++)
                {
                    f[i][j][k]+=f[i-1][w][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 sum=0,res=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(-sum,p)];
        }
        sum+=x;
        if(!i&&sum%p==0)res++;
    }
    return res;
}
int main()
{
    while(cin>>l>>r>>p)
    {
        init();
        cout<<dp(r)-dp(l-1)<<endl;
    }
    return 0;
}