HDU-6156 Palindrome Function

HDU-6156 Palindrome Function

#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define itn int
using namespace std;
const int N=2e5;
const long long mod=1e9+7;
const long long mod2=998244353;
const int oo=0x7fffffff;
const int sup=0x80000000;
typedef long long ll;
typedef unsigned long long ull;
template <typename it>void db(it *begin,it *end){while(begin!=end)cout<<(*begin++)<<" ";puts("");}
template <typename it>
string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;}
template <typename it>int o(it a){cout<<a<<endl;return 0;}
ll mul(ll a,ll b,ll c){ll ans=0;for(;b;b>>=1,a=(a+a)%c)if(b&1)ans=(ans+a)%c;return ans;}
ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=mul(a,a,c))if(b&1)ans=mul(ans,a,c);return ans;}
ll dp[N][37];
ll get(int k,int base){
    ll res,cnt=0,w=0,num=base-1,half=1;
    while(1){
        if(w>0&&w%2==0)num*=base;
        w++;
        if(cnt+num>=k)break;
        cnt+=num;
    }
    k=k-cnt-1;
    for(int i=0;i<(w-1)/2;i++)
        half*=base;
    half+=k;
    res=half;
    if(w%2==1)half/=base;
    while(half){
        res=res*base+half%base;
        half/=base;
    }
    return res;
}
int count(int x,int base){
    if(x==1)return 1;
    if(x==0)return 0;
    int l=1,r=200000-1;
    int ans=0;
    while(r>=l){
        int mid=l+r>>1;
        if(dp[mid][base]>x)r=mid-1;
        else ans=mid,l=mid+1;
    }
    return ans;
}
void pre(){
    for(int i=1;i<200000;i++){
        for(int j=2;j<=36;j++)dp[i][j]=get(i,j);
    }
}
int main(){
    pre();
    //freopen("in.txt","r",stdin);
    int t;cin>>t;
    for(int cas=1;cas<=t;cas++){
        int L,R,l,r;
        sc("%d%d%d%d",&L,&R,&l,&r);
        ll ans=1LL*(R-L+1)*(r-l+1);
        for(int base=l;base<=r;base++){
            int num=count(R,base)-count(L-1,base);
            ans+=1LL*num*(base-1);
        }
        printf("Case #%d: %lld\n",cas,ans);
    }
}