1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int B=40;
int dig[B],tmp[B];
ll dp[B][B][B];
int base;
ll dfs(int pos,int start,bool limit)
{
if (pos<0) return 1;
if (!limit&&dp[base][pos][start]!=-1) {
return dp[base][pos][start];
}
int last=limit?dig[pos]:base-1;
ll res=0;
for (int i=0;i<=last;i++) {
tmp[pos]=i;
if (pos==start&&i==0) {
res+=dfs(pos-1,start-1,limit&&(i==last));
} else if (pos<(start+1)/2) {
if (i==tmp[start-pos]) {
res+=dfs(pos-1,start,limit&&(i==last));
}
} else {
res+=dfs(pos-1,start,limit&&(i==last));
}
}
if (!limit) dp[base][pos][start]=res;
return res;
}
ll calc(int x)
{
int len=0;
while (x) {
dig[len++]=x%base;
x/=base;
}
return dfs(len-1,len-1,1);
}
int main()
{
memset(dp,-1,sizeof(dp));
int T,cas=0;
scanf("%d",&T);
while (T--) {
int L,R,l,r;
scanf("%d%d%d%d",&L,&R,&l,&r);
ll ans=0;
for (base=l;base<=r;base++) {
ll cnt=calc(R)-calc(L-1);
ans+=cnt*base+(R-L+1-cnt);
}
printf("Case #%d: %lld\n",++cas,ans);
}
return 0;
}
|
