数位dp，我们肯定枚举集合的位置，但是如果每次都重新dp的话会很麻烦，所以我们可以先钦定在最低位集合，dp出代价，然后再一步步找到正确的集合点，每次更改的代价也dp算就好了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#define int long long
using namespace std;
int L,R,K;
int a[];
int f[][];
int dfs(int pos,int sum,int lim){
if(!pos)return sum;
if(!lim&&f[pos][sum]!=-)return f[pos][sum];
int up=lim?a[pos]:K-;
int ans=;
for(int i=;i<=up;i++)
ans+=dfs(pos-,sum+(pos-)*i,lim&&(i==up));
if(!lim)f[pos][sum]=ans;
return ans;
}
int dfs(int pos,int zd,int sum,int lim){
if(sum<)return ;
if(!pos)return sum;
if(!lim&&f[pos][sum]!=-)return f[pos][sum];
int up=lim?a[pos]:K-;
int ans=;
for(int i=;i<=up;i++){
if(pos>=zd)ans+=dfs(pos-,zd,sum+i,lim&&(i==up));
else ans+=dfs(pos-,zd,sum-i,lim&&(i==up));
}
if(!lim)f[pos][sum]=ans;
return ans;
}
int work(int x){
int pos=;
while(x){
a[++pos]=x%K;
x/=K;
}
memset(f,-,sizeof f);
int ans=dfs(pos,,);
for(int i=;i<=pos;i++){
memset(f,-,sizeof f);
ans-=dfs(pos,i,,);
}
return ans;
}
signed main(){
scanf("%lld%lld%lld",&L,&R,&K);
printf("%lld\n",work(R)-work(L-));
return ;
}