http://acm.hdu.edu.cn/showproblem.php?pid=6156
【AC】
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const ll mod=1e9+7; 5 int num[50]; 6 int L,R,l,r; 7 ll query(int x,int k) 8 { 9 if(x==0) return 0; 10 int cnt=0; 11 int cp=x; 12 while(cp) 13 { 14 num[cnt++]=cp%k; 15 cp/=k; 16 } 17 int base=k,sum=1,tot=0; 18 for(int i=1;i<cnt;i++) 19 { 20 tot+=base-sum; 21 if(i%2==0) 22 { 23 sum=base; 24 base*=k; 25 } 26 } 27 int p=0; 28 for(int i=cnt-1;i>=cnt/2;i--) 29 { 30 p=p*k+num[i]; 31 } 32 tot+=p-sum; 33 int o=(cnt%2==0?cnt/2:cnt/2+1); 34 for(int i=o;i<cnt;i++) 35 { 36 p=p*k+num[i]; 37 } 38 if(p<=x) tot+=1; 39 return 1ll*tot*(k-1)+(ll)x; 40 } 41 int main() 42 { 43 int T; 44 scanf("%d",&T); 45 int cas=0; 46 while(T--) 47 { 48 scanf("%d%d%d%d",&L,&R,&l,&r); 49 ll ans=0; 50 for(int i=l;i<=r;i++) 51 { 52 ans+=query(R,i)-query(L-1,i); 53 } 54 printf("Case #%d: %I64d ",++cas,ans); 55 } 56 return 0; 57 }