题目连接：hdu_5085_Counting problem
题意：给你一个计算公式，然后给你一个区间，问这个区间内满足条件的数有多少个
题解：由于这个公式比较特殊，具有可加性，我们考虑讲一个数分为两个部分，这样就可以用莫队的思想均摊时间复杂度，将9位数分为一个4位和一个5位，这里我感觉sqr为10000 速度比较快。然后如果b小于sqr，那么直接暴力就行，如果b大于sqr,那么我们要把a和b都分为头部和尾部（注意是闭区间，a需要减1），如果a小于sqr，那么他的头部就为0，然后计算0-a的尾部，并将相应的值插入Hash表，然后计算以a头部开头满足条件的数，记为reta，同理，计算0-b的尾部，记为retb，如果b尾小于a尾，就要先计算b再计算a，然后将0到sqr-1的数对应的值也全部插入Hash表，然后从a的头到b的头，寻找对应的值，这里要用一下容斥定理，retb-reta就是从[a,b]之间满条件的数的个数.
#include<cstdio>
#define F(i,a,b) for(int i=a;i<=b;i++)
typedef long long LL; const LL M=(<<)-,N=1e5+,sqr=1e4;
LL K,a,b,ahd,bhd,bt,at,reta,retb,T,S,dt[][];
inline LL pow(LL x,LL k){
LL an=;
while(k){
if(k&)an*=x;
k>>=,x*=x;
}
return an;
}
//------------Hash table------------------------
struct E{LL key;LL cnt;E *nxt;}*g[M+],pool[N],*cur=pool,*p;LL vis[M+];
void init_Hash(){T++,cur=pool;}
inline void ins(LL key){
if(key>S)return;
LL u=key&M;
if(vis[u]<T)vis[u]=T,g[u]=NULL;
for(p=g[u];p;p=p->nxt)if(p->key==key){p->cnt++;return;}
p=cur++,p->key=key,p->cnt=,p->nxt=g[u],g[u]=p;
} inline LL ask(LL key){
if(key<)return ;
LL u=key&M;
if(vis[u]<T)return ;
for(p=g[u];p;p=p->nxt)if(p->key==key)return p->cnt;
return ;
}
//----------------------------------------------
inline LL cal(LL x){
LL an=;
while(x)an+=dt[x%][K],x/=;
return an;
}
void init(){F(i,,)F(j,,)dt[i][j]=pow(i,j);}
int main(){
init();
while(~scanf("%lld%lld%lld%lld",&a,&b,&K,&S)){
init_Hash();
ahd=(a-)/sqr,bhd=b/sqr,at=(a-)%sqr,bt=b%sqr;
if(at<bt){
F(i,,at)ins(cal(i));
reta=ask(S-cal(ahd));
F(i,at+,bt)ins(cal(i));
retb=ask(S-cal(bhd));
F(i,bt+,sqr-)ins(cal(i));
}else{
F(i,,bt)ins(cal(i));
retb=ask(S-cal(bhd));
F(i,bt+,at)ins(cal(i));
reta=ask(S-cal(ahd));
F(i,at+,sqr-)ins(cal(i));
}
F(i,ahd,bhd-)retb+=ask(S-cal(i));
printf("%lld\n",retb-reta);
}
return ;
}