本来想找道水题，结果，，，
我又被坑了，，
捣鼓了半天出的思路，打了一个晚自习，A了后一找题解，发现大家想的好像都和我不一样，，
翻了一会儿，猛然发现还是有dalao跟我想的一样Orz，写得比身为魔芋的我好多了，，于是，就（Ctrl C+Ctrl V）借鉴了一波
但是，，我还是把我的丑鬼代码存个档吧
对于每个数，它一定会在集合点为某一位，然后该集合点数为0~k-1的某值时被找到（把所有石子移到集合点）
那么，我们可以枚举集合点(mid)与集合点的数(midv)，在套上数位dp,就可以得到答案
怎么套?
如果能转移，那么我们的代价必须减少。
mid左移一位，改变量为S2+midv-S1;
mid右移一位，改变量为S1+midv-S2;
那么，得到某个数时，我们的要求就是改变量>=0，即改变量>=-midv且改变量<=midv，满足的话这个数最优解就是这种情况，反之则不是
去重变成左开右闭
找每一位，变化量，是否被限制，我们就可以得到花费
记忆化爆搜即可
在下自以为注释写得还行，是在没懂可以看看（非主流做法，被带歪了别怪我）
//注：方案数实为在这种方案，即mid与midv为枚举出的定值时最优的数的个数 #include<bits/stdc++.h> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<algorithm> #include<queue> #include<deque> #include<list> #include<set> #include<vector> #include<iostream> #define ll long long #define re register #define inf 0x3f3f3f3f #define inl inline #define sqr(x) (x*x) //#define eps 1e-8 #define debug printf("debug "); //#pragma comment(linker, "/STACK:1024000000,1024000000") //#pragma GCC optimize (2) //#pragma G++ optimize (2) using namespace std; //const ll mod; const ll MAXN=3e5+10; inl ll read() { re ll x = 0; re int f = 1; char ch = getchar(); while(ch<'0'||ch>'9') { if(ch== '-' ) f = -1; ch = getchar(); } while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x * f; } inl char readc() { char ch=getchar(); while(('z'<ch||ch<'a')&&('Z'<ch||ch<'A')) ch=getchar(); return ch; } inl void write(re ll x){ if(x>=10)write(x/10); putchar(x%10+'0'); } inl void writeln(re ll x){ if(x<0) {x=-x;putchar('-');} write(x); puts(""); } inl ll gcd(re ll x,re ll y){while(y^=x^=y^=x%=y);return x;} inl void FR() { freopen(".in","r",stdin); freopen(".out","w",stdout); } inl void FC() { fclose(stdin); fclose(stdout); } ll l,r,k,cnt,mid,midv,a[50];//集合点是第几位，集合点那个数是多少 ll f[60][505][2],g[60][505][2];//f表示费用 ，g表示方案数 ll dp(ll x,ll y,ll t) { if(x==cnt+1) return 0; return f[x][y][t]; }//找花费(已在solve中求解出) ll solve(ll x,ll y,bool limit) {//第几位，S2-S1，是否被限制 if(x==cnt+1) { re ll ssy=y-250; if(ssy>-midv&&ssy<=midv) return 1;//改变量为：S2(mid后面的和)-S1(mid前面的和)+midv(集合点的数的个数) else return 0; }//最后一位，如果可行返回1，反之则0 if(~f[x][y][limit]) return g[x][y][limit];//求过方案，直接返回 re ll ans=0,num=0; if(x==mid) { if(!limit || midv<=a[x]) { ans+=solve(x+1,y,limit&(midv==a[x])); num+=dp(x+1,y,limit&(midv==a[x])); }//+限制，不可乱跑方案与花费+不限制，可乱跑方案与花费 }//刚好第mid位 else if (limit) { for (re ll i=0;i<=a[x];i++) { re ll sum=i*((x>mid)?-1:1);//左边或右边多了一些数 re ll t=solve(x+1,y+sum,i==a[x]);//往后找方案数 ans+=t; num+=abs(x-mid)*i*t+dp(x+1,y+sum,i==a[x]);//花费加上这一段方案数(这么选是最优解的数的个数)*这一位是多少*这一段位移长度+后面的花费 //因为如果这一位可行，那么这一位-1得到的数一定也是以mid,midv取该值为最优，所以*i } }//被限制 else if (!limit) { for (re ll i=0;i<k;i++) { re ll sum=i*((x>mid)?-1:1); re ll t=solve(x+1,y+sum,0); ans+=t; num+=abs(x-mid)*i*t+dp(x+1,y+sum,0); } }//无限制，与上面类似 f[x][y][limit]=num; return g[x][y][limit]=ans;//记忆化 } ll calc(ll x) { re ll ans=0;cnt=0; while(x) {a[++cnt]=x%k;x/=k;} for(re ll i=1;i<=cnt/2;i++) swap(a[i],a[cnt-i+1]); for(mid=1;mid<=cnt;mid++) { for(midv=1;midv<k;midv++) { memset(g,0,sizeof(g)); memset(f,-1,sizeof(f)); solve(1,250,1); ans+=f[1][250][1];//后面最多13个(L,R<=1e15，L或R等于1e15时后面14个全是0)，13*19=247,卡一下 (祭奠一下在下这个开500的蒟蒻) } } return ans; } int main(){ // FR(); l=read(),r=read(),k=read(); writeln(calc(r)-calc(l-1)); // FC(); return 0; }