我是靠谱客的博主 忧伤保温杯，这篇文章主要介绍ICPC2019徐州区域赛复现赛C < 3 numbersF. The Answer to the Ultimate Question of Life, The Universe, and Everything.Cat，现在分享给大家，希望可以做个参考。
C < 3 numbers
教训就是不能看见素数就不管三七二十一直接上线性筛板子，还是需要多仔细想想题意。
题解：
解法一
这是一道素数密度的题目，首先需要推出一个结论。一个常识就是素数越往后是越来越分散的。观察素数表以后可以发现从100左右开始，如果区间长度超过了50（估计值），那么区间内的素数一定小于1/3.。如果区间的长度小于50，那么对于这个区间内的所有数做一遍√n的素数判断就可以。
代码：
复制代码
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#include<bits/stdc++.h> #define ll long long #define inf 0x3f3f3f3f #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define endl 'n' using namespace std; int b[25] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97}; const int N = 1e5 + 100; bool prime(int x) { for(int i = 0; i < 25; i ++) { if(x % b[i] == 0 && x != b[i]) return 0; } return 1; } int main() { int t; scanf("%d", &t); while(t --) { int l, r; scanf("%d%d", &l, &r); if(l == r) { if(l == 1 || prime(l) == 1) puts("No"); else puts("Yes"); } else if(r >= 100 && r - l > 50) puts("Yes"); else { ll ans = 0; int bj = 0; int len = r - l + 1; for(int i = l; i <= r; i ++) { if(prime(i)) ans ++; if(ans * 3 >= len) { puts("No"); bj = 1; break; } } if(!bj) puts("Yes"); } } return 0; }
解法二
可以使用Robin-Miller 素数测试来判断素数,复杂度O(MAX log（n）)。
复制代码
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#include <bits/stdc++.h> #define inf 0x3f3f3f3f #define fi first #define se second #define endl 'n' #define Sezuna 0 #define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0) using namespace std; typedef long long ll; const ll INF = 0x3f3f3f3f3f3f3f3f; const int N = 1e6 + 100; long long PowerMod(long long a, long long b, long long k) { long long ret = 1, f = a; while (b) { if (b & 1) ret = ret * f % k; f = f * f % k; b >>= 1; } return ret; } bool MillerRobin(long long n,int MAX) { int i; long long tmp; srand(100); for (i = 0; i < MAX; i++) { tmp = rand() % (n - 1) + 1; if (PowerMod(tmp, n - 1, n) != 1) break; } return (i == MAX); } int main() { int t; scanf("%d", &t); while(t --) { int bj = 0; ll l, r; ll ans = 0; scanf("%lld%lld", &l, &r); ll len = r - l + 1; if(l == r) { if(l == 1 || MillerRobin(l, 50) == 1) puts("No"); else puts("Yes"); } else if(r >= 100 && len > 100) puts("Yes"); else { if(l == 1) l ++, ans ++; for(ll i = l; i <= r; i ++) { if(MillerRobin(i, 50)) ans ++; if(ans * 3 >= len) { puts("No"); bj = 1; break; } } if(!bj) puts("Yes"); } } return Sezuna; }
F. The Answer to the Ultimate Question of Life, The Universe, and Everything.
题解：
真·打表题。
考虑暴力的复杂度是 枚举 a3 + b3的和（复杂度10000*10000），然后二分找c3是否存在，但是明显得先将c3排序，O(10000log(10000))，复杂度显然已经超出1s了。
仔细观察发现x的范围只有0 - 200，所以可以先将所有x对应的a b c的情况打表打出来，然后复制放到二维数组里，直接输出答案。
打表代码：
复制代码
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#include <bits/stdc++.h> #define inf 0x3f3f3f3f #define fi first #define se second #define endl 'n' #define Sezuna 0 #define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0) #pragma GCC optimize(2) #pragma GCC optimize(3,"Ofast","inline") using namespace std; typedef long long ll; const ll INF = 0x3f3f3f3f3f3f3f3f; const int N = 1e6 + 100; unordered_map<ll, int> f; ll g(ll x) // { //x可能为负，也可能为正，所以需要从-5000开始 for(ll i = -5000; i <= 5000; i ++) //这里的i得用ll，因为下面关系到i^3的运算 if(i * i * i == x) return i; } bool find(int x) { for(ll i = 0; i <= 5000; i ++) //这里可以分类讨论，减少循环次数，不用从-5000开始 { for(ll j = 0; j <= 5000; j ++) { //x = -i -j +g if(f.count(x + i * i * i + j * j * j)) //如果存在这个c^3 { printf("%lld, %lld, %lld,n", -i, -j, g(x + i * i * i + j * j * j)); return true; } //x = +i +i -g else if(f.count(i * i * i + j * j * j - x)) //这里找的是正的g是否存在,而我们实际上的g是负的，所以开根之后要取负 { // printf("%lld %lld %lld = %dn",i,j,g(i*i*i+j*j*j-x),x); printf("%lld, %lld, %lld,n", i, j, g(i * i * i + j * j * j - x) == 0 ? 0 : -g(i * i * i + j * j * j - x)); return true; } } } return false; } int main() { f.clear(); freopen("1.in", "w", stdout); for(ll i = -5000; i <= 5000; i ++) //先用hash存下c^3的所有结果 f[i * i * i] = 1; for(int i = 0; i <= 200; i ++) { if(!find(i)) printf("1111111111,0,0,n"); else continue; } return Sezuna; }
AC代码:
复制代码
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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234#include <bits/stdc++.h> #define inf 0x3f3f3f3f #define fi first #define se second #define endl 'n' #define Sezuna 0 #define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0) using namespace std; typedef long long ll; const ll INF = 0x3f3f3f3f3f3f3f3f; const int N = 1e6 + 100; int ans[205][3] = { 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, -1, -1, 2, 0, -1, 2, 0, 0, 2, 0, 1, 2, 1, 1, 2, -2, -2, 3, 7, 10, -11, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, 2, 2, -1, 0, 2, 2, 1, 2, 2, -1, -2, 3, 0, -2, 3, 1, 3, -2, -11, -14, 16, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, 2, 2, 2, -1, -1, 3, 0, -1, 3, 0, 0, 3, 0, 1, 3, 1, 1, 3, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, 2, 3, -1, 0, 2, 3, 1, 2, 3, 0, -3, 4, 1, 4, -3, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, 2, 2, 3, -5, -7, 8, 2, 4, -3, 3, 3, -2, 6, 7, -8, -2, -2, 4, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, 602, 659, -796, 1111111111,1111111111,1111111111, -2, -4, 5, 0, 3, 3, -1, -2, 4, 0, -2, 4, 1, 4, -2, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, -1, -4, 5, 0, -4, 5, -1, -1, 4, 0, -1, 4, 0, 0, 4, 0, 1, 4, 1, 1, 4, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, 2, 5, -4, 11, 20, -21, 2, 4, -1, 0, 2, 4, 1, 2, 4, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, 26, 53, -55, -19, -33, 35, 2, 2, 4, 3, 3, 3, -11, -11, 14, -2, -5, 6, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, -1972, -4126, 4271, 3, 5, -4, 6, 6, -7, -1, -5, 6, 0, 3, 4, 1, 3, 4, -5, -5, 7, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, 14, 20, -22, -1, -3, 5, 0, -3, 5, 1, 5, -3, -3, -6, 7, 4, 4, -3, 118, 229, -239, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, -4, -7, 8, 2, 5, -3, -28, -48, 51, -948, -1165, 1345, -2, -2, 5, 1111111111,1111111111,1111111111, 148, 1039, -1040, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, -6, -10, 11, -1, -2, 5, 0, -2, 5, 1, 5, -2, -2, -6, 7, 4, 4, -2, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, -1, -1, 5, 0, -1, 5, 0, 0, 5, 0, 1, 5, 0, -6, 7, 0, 4, 4, 1, 4, 4, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, 2, 5, -1, 0, 2, 5, 1, 2, 5, 2, 7, -6, 2, 4, 4, -9, -11, 13, -77, -86, 103, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, 2, 2, 5, -3, -7, 8, 1111111111,1111111111,1111111111, -2, -4, 6, -7, -8, 10, -5, -9, 10, -50, -56, 67, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, 260, 317, -367, -1, -4, 6, 0, 3, 5, 1, 3, 5, 3, 7, -6, 3, 4, 4, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, 80, 119, -130, 2, 3, 5, -2, -7, 8, -3, -3, 6, -21, -26, 30, -45, -47, 58, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, -1, -7, 8, 0, -7, 8, 1, 8, -7, -5, -6, 8, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, 7, 7, -8, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, 2, 8, -7, -10, -13, 15, 3, 3, 5, 1111111111,1111111111,1111111111, -2, -3, 6, 9, 13, -14, 10, 16, -17, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, 5, 5, -4, 27, 56, -58, -1, -3, 6, 0, -3, 6, 1, 4, 5, -3, -5, 7, 4, 4, 4, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, 1111111111,1111111111,1111111111, 3, 8, -7, 2, 4, 5, -19, -48, 49, 15, 22, -24, -2, -2, 6, }; int main() { int t; scanf("%d", &t); while(t --) { int x; scanf("%d", &x); if(ans[x][0] == 1111111111) puts("impossible"); else printf("%d %d %dn", ans[x][0], ans[x][1], ans[x][2]); } return Sezuna; }
Cat
（待补）
规律题。
用到的定理：
异或和定理：令f(n)表示从1到n的异或和，则：
若n≡0(mod4)，f(0,n)=n，
若n≡1(mod4)，f(0,n)=1，
若n≡2(mod4)，f(0,n)=n+1，
若n≡3(mod4)，f(0,n)=0。若a是偶数，且a%4=(b+3)%4，则[a,b]的区间异或和为0。
异或运算的作用
参与运算的两个值，如果两个相应bit位相同，则结果为0，否则为1。
即：
0^0 = 0，
1^0 = 1，
0^1 = 1，
1^1 = 0
按位异或的3个特点：
（1） 0^0=0，0^1=1 0异或任何数＝任何数
（2） 1^0=1，1^1=0 1异或任何数－任何数取反
（3） 任何数异或自己＝把自己置0
最后
以上就是忧伤保温杯最近收集整理的关于ICPC2019徐州区域赛复现赛C < 3 numbersF. The Answer to the Ultimate Question of Life, The Universe, and Everything.Cat的全部内容，更多相关ICPC2019徐州区域赛复现赛C内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复