#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=1e5+5;
const int maxn=1e6+5;
typedef long long ll;
ll dp[50][50][40][2];
int dig[50];
int tmp[50];
ll dfs(int len,int st,bool is,int jin,bool e)
{
if(len<0)
return is;
if(!e&&dp[st][len][jin][is]!=-1)
return dp[st][len][jin][is];
ll ans=0;
int d=e?dig[len]:jin-1;
for(int i=0;i<=d;i++)
{
tmp[len]=i;
if(i==0&&st==len)
ans=ans+dfs(len-1,st-1,is,jin,e&&(i==d));
else if(is&&len<(st+1)/2)
ans=ans+dfs(len-1,st,is&&(i==tmp[st-len]),jin,e&&(i==d));
else
ans=ans+dfs(len-1,st,is,jin,e&&(i==d));
}
if(!e)
dp[st][len][jin][is]=ans;
return ans;
}
ll solve(int a,int jin)
{
int cnt=0;
if(a==0)
return 1;
while(a)
{
dig[cnt++]=a%jin;
a=a/jin;
}
return dfs(cnt-1,cnt-1,1,jin,1);
}
int main()
{
int t;
scanf("%d",&t);
int ca=1;
memset(dp,-1,sizeof(dp));
while(t--)
{
int l1,r1,l2,r2;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
ll ans=0;
for(int i=l2;i<=r2;i++)
{
ll b=solve(r1,i)-solve(l1-1,i);
ans=ans+b*i+(r1-l1+1-b);
}
printf("Case #%d: %lld\n",ca++,ans);
}
return 0;
}
来源: http://www.bubuko.com/infodetail-2272320.html