/
Q2-BoringNumber.cpp
152 lines (138 loc) · 4.55 KB
/
Q2-BoringNumber.cpp
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
/***********************************************
♡ Filename : 2020H-Q2-BoringNumber.cpp
♡
♡ Description : ---
♡ Author : Li Xudong
♡ Contact : 757264690@qq.com
♡ Created : 2020-11-26 22:22:28
***********************************************/
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <strstream>
using namespace std;
// 如果直接遍历，然后对每个数的每一位求奇偶性，则test1可以通过
// 但是test2数据太大，直接遍历则超时。
// 可以用组合数学的思想来做。
// 比如我们有一个数9734，我们计算1000到9734间一共有多少个符合题目的数字。
// 对于第1位（奇位），而小于9的奇数有4个，则如果以这4个奇数为第1位，则有4*5*5*5个数。
// 因为第1位为9，是奇数，因此可以考虑对第2位进行计算，
// 对于第2位（偶位），而小于7的偶数有4个，则如果以9为第一位，这4个偶数为第2位，则有1*4*5*5个数。
// 因为第2位为7，是奇数，因此结束计算（后面的数一定不符合）
//
// 那么0-9734中有多少个满足条件的数呢？
// 对于4位的数，可以按照上面的方法做；对于3位数，应该有5^3个；对于2位数，应该有5^2个；对于1位数，应该有5^1个。
//
// 那么比如计算123-9734中有多少个满足的数呢？
// 我们可以转化为求(0-9724)的个数减去(0-123)的个数。
//
// 其中，因为对于2位数和1位数，两者是重复的，减去之后为0，因此可以免去计算。
// L 和 R 范围是1-1e18，longlong比较保险
typedef long long ll;
// 1,2,3……之前（包括）一共有多少个偶数
int under_even[10]={1,1,2,2,3,3,4,4,5,5};
// 一共有少个奇数
int under_odd[10]={0,1,1,2,2,3,3,4,4,5};
// longlong转string
string lltoString(long long t)
{
std::string result;
std::strstream ss;
ss << t;
ss >> result;
return result;
}
// 对每一位，计算 剩余的奇/偶数，然后乘以len-1个5
ll cnt_part(int res, int len)
{
ll ans = 0;
int i;
ans = res;
for(i=1; i<len; i++)
{
ans *= 5;
}
return ans;
}
// 计算个数，例如1000-1234之间符合条件的个数
ll cnt_ans(string num)
{
int len = num.length();
int i;
// 奇偶位标记
bool flag = false;
ll ans = 0;
ll res = 0;
// 对每一位进行遍历
for(i=0; i<len; i++)
{
flag = !flag;
// 当前是奇数位
if(flag)
{
// 计算可选择的奇数个数
if((num[i]-'0')%2) res = under_odd[num[i]-'0']-1;
else res = under_odd[num[i]-'0'];
// 可选择数*5*5*5……
if(res>0) ans += cnt_part(res, len-i);
// 如果当前的数也是奇数，则可以对下一位进行计算
if((num[i]-'0')%2)
continue;
// 如果当前数不是奇数，则后面的数都不是了，则停止遍历
else
break;
}
// 当前是偶数位
else
{
if(!((num[i]-'0')%2)) res = under_even[num[i]-'0']-1;
else res = under_even[num[i]-'0'];
if(res>0) ans += cnt_part(res, len-i);
if(!((num[i]-'0')%2))
continue;
else
break;
}
}
// 因为之前判断可选择的奇偶个数的时候，没有包括这个数本身
// 因此遍历到最后一位的时候，需要再特殊判断一下最后一位是否满足，若满足加1
// i==len 遍历到最后一位
// len%2 判断最后一位是奇数还是偶数
if(i==len && len%2 && (num[len-1]-'0')%2)
ans++;
if(i==len && !(len%2) && !((num[len]-'0')%2))
ans ++;
return ans;
}
void solve()
{
ll L,R;
string num_L, num_R;
long long ans1, ans2, ans3;
int i,j;
ans1 = ans2 = ans3 = 0;
scanf("%lld %lld", &L, &R);
num_L = lltoString(L-1);
num_R = lltoString(R);
ans1 = cnt_ans(num_L);
ans2 = cnt_ans(num_R);
// 若两个数的位数不一样
// 比如，56-1575
// 函数计算的是0-55之间的个数和1000-1575之间的个数
// 因此对于后者，需要加上位数为3和位数为2时，符合条件的个数
// 分别是5^3,5^2
for(i=num_L.length(); i<num_R.length(); i++)
ans3 += pow(5,i);
printf("%lld\n", ans2+ans3-ans1);
}
int main()
{
int t,T;
scanf("%d", &T);
for(t=1; t<=T; t++)
{
printf("Case #%d: ", t);
solve();
}
}