先考虑，对于确定的一个数，怎样移动代价最少（或者移到哪个位置最优）？
假设我们都移到下标\(1\)位置（设集合点为\(1\)），那么移动到下标\(2\)与\(1\)相比代价差为：\(下标<1的石子数和-下标>1的石子数和\)。
如果它为负，那么把移到\(1\)的代价加上它，令集合点变为\(2\)...
这样一直改变集合点，直到 \(下标<p的石子数和 \geq 下标>p的石子数和\)。那么移到\(p\)就是最优的。
这样感觉很对。怎么证明？
我们发现式子左边其实就是前缀和，右边是后缀和。因为石子数非负，所以随着\(p\)移动，前缀和是递增的，后缀和递减。
即如果出现 \(前缀和 \geq 后缀和\) 的情况，前缀和就永远大于等于后缀和了。
那么我们对\([l,r]\)的所有数都进行这个贪心。
首先我们要算出所有数集合到1的代价和。这个可以用数位DP算出（递推数的个数，用个数求和）。
然后枚举\(p=2\sim n\)位，我们可以求 以\(p\)为分界，前缀数位和 小于 后缀数位和 且 在\([0,r]\) 的数的个数。其中每个数会减少的代价就是\(前缀和-后缀和\)。
因为数位和最多差不多是230，可以直接枚举这两个状态。同样数位DP。
\(f[i][j][k][0/1]\)表示当前到第\(i\)位，总数位和为\(j\)，\(p\)位之前的数位和为\(k\)，是否到上界，的数的个数。
另外还可以直接减掉\(k\)那一维。。
记忆化就好写的多了（还快）。
//49592kb 404ms
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
const int N=52,M=245;
int A[N];
LL g[N][2],sum[N][2],f[N][M][M][2];
LL Calc(LL x,int base)
{
int n=0;
for(; x; x/=base) A[++n]=x%base;
std::reverse(A+1,A+1+n);//
memset(g,0,sizeof g), memset(sum,0,sizeof sum);
g[0][1]=1;
for(int i=0; i<n; ++i)//好像还是从0方便。。
{
LL v=g[i][1]; int ai=A[i+1];
g[i+1][1]+=v, sum[i+1][1]=sum[i][1]+v*i*ai;
for(int j=0; j<ai; ++j) g[i+1][0]+=v, sum[i+1][0]+=sum[i][1]+v*i*j;
v=g[i][0];
for(int j=0; j<base; ++j) g[i+1][0]+=v, sum[i+1][0]+=sum[i][0]+v*i*j;
}
LL ans=sum[n][0]+sum[n][1];
for(int p=1; p<n; ++p)
{
f[0][0][0][1]=1;
for(int i=0; i<n; ++i)
{
int ai=A[i+1];
if(i+1<=p)
{
LL v;
for(int j=0,lim=i*(base-1); j<=lim; ++j)
{
if(v=f[i][j][j][1])//好不直观。。
{
f[i+1][j+ai][j+ai][1]+=v;//+=
for(int k=0; k<ai; ++k) f[i+1][j+k][j+k][0]+=v;
}
if(v=f[i][j][j][0])
for(int k=0; k<base; ++k) f[i+1][j+k][j+k][0]+=v;
}
}
else
{
LL v;
for(int j=0,lim=i*(base-1); j<=lim; ++j)
for(int k=0,lim2=p*(base-1); k<=lim2; ++k)
{
if(v=f[i][j][k][1])
{
f[i+1][j+ai][k][1]+=v;
for(int l=0; l<ai; ++l) f[i+1][j+l][k][0]+=v;
}
if(v=f[i][j][k][0])
for(int l=0; l<base; ++l) f[i+1][j+l][k][0]+=v;
}
}
}
for(int i=0,lim=p*(base-1); i<=lim; ++i)//pre
for(int j=i+1,lim2=n*(base-1); i+j<=lim2; ++j)//suf
ans+=(i-j)*(f[n][i+j][i][0]+f[n][i+j][i][1]);
for(int i=1; i<=n; ++i)
for(int j=0,lim=i*(base-1); j<=lim; ++j)
for(int k=0,lim2=p*(base-1); k<=lim2; ++k)
f[i][j][k][0]=0, f[i][j][k][1]=0;
}
return ans;
}
int main()
{
LL L,R; int K; scanf("%lld%lld%d",&L,&R,&K);
printf("%lld\n",Calc(R,K)-Calc(L-1,K));
return 0;
}