碎碎念
灵异事件：第七行的灵异事件，导致在执行模式执行cout能不输出结果，在debug模式执行cout能输出结果
代码语言：javascript复制 vector<pair<int, bool>> prime_table(100001, {0, true});
prime_table[0].second = false;
prime_table[1].second = false;
int ans = 1;
prime_table[2].first = 0;
for (int i = 3; i <= 100001; i = 2) {
...
}
- c 标准不要求vector::operator[]进行下标越界检查，原因是为了效率，总是强制下标越界检查会增加程序的性能开销；
看题解的时候，本想膜拜一下执行用时4ms的大神，结果点进去竟然是打表！！！世界崩塌的感觉，重点是，这还是个初段大神啊！！！初段诶！
代码语言：javascript复制 Would you please return 0;
这句才是精粹，打表什么的就让我们忘记它吧(*￣︶￣)
标签
- 数学、质数、累计和
题目地址
- D - 2017-like Number
- https://atcoder.jp/contests/abc084/tasks/abc084_d
题目描述
Input
Input is given from Standard Input in the following format:
代码语言：javascript复制Q
l1 r1
:
lQ rQ
Output
Print Q lines. The i-th line (1≤i≤Q) should contain the response to the i-th query.
Sample Input 1
代码语言：javascript复制1
3 7
Sample Output 1
代码语言：javascript复制2
- 3 is similar to 2017, since both 3 and (3 1)/2=2 are prime.
- 5 is similar to 2017, since both 5 and (5 1)/2=3 are prime.
- 7 is not similar to 2017, since (7 1)/2=4 is not prime, although 7 is prime.
Thus, the response to the first query should be 2.
Sample Input 2
代码语言：javascript复制4
13 13
7 11
7 11
2017 2017
Sample Output 2
代码语言：javascript复制1
0
0
1
Note that 2017 is also similar to 2017.
Sample Input 3
代码语言：javascript复制6
1 53
13 91
37 55
19 51
73 91
13 49
Sample Output 3
代码语言：javascript复制4
4
1
1
1
2
题解
小码匠题解
代码语言：javascript复制void coder_solution() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int q;
cin >> q;
vector<bool> prime_table(100001, true);
vector<int> count_prime_table(100001, 0);
prime_table[0] = false;
prime_table[1] = false;
prime_table[2] = true;
for (int j = 2; j * 2 < 100001; j) {
prime_table[j * 2] = false;
}
for (int i = 3; i < 100001; i = 2) {
if (prime_table[i]) {
for (int j = 2; j * i <= 100001; j) {
prime_table[j * i] = false;
}
} else {
prime_table[i 1] = false;
}
count_prime_table[i] = count_prime_table[i - 1];
if (prime_table[i] && prime_table[(i 1) / 2]) {
count_prime_table[i] ;
}
count_prime_table[i 1] = count_prime_table[i];
}
int l, r;
for (int i = 0; i < q; i) {
cin >> l >> r;
cout << count_prime_table[r] - count_prime_table[l - 1] << endl;
}
}
参考题解
代码语言：javascript复制void best_solution() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// エラトステネスのふるい
int MAX = 101010;
vector<int> is_prime(MAX, 1);
is_prime[0] = 0, is_prime[1] = 0;
for (int i = 2; i < MAX; i) {
if (!is_prime[i]) continue;
for (int j = i * 2; j < MAX; j = i) is_prime[j] = 0;
}
// 2017-like 数かどうか
vector<int> a(MAX, 0);
for (int i = 0; i < MAX; i) {
if (i % 2 == 0) continue;
if (is_prime[i] && is_prime[(i 1) / 2]) a[i] = 1;
}
// 累積和
vector<int> s(MAX 1, 0);
for (int i = 0; i < MAX; i) s[i 1] = s[i] a[i];
// クエリ処理
int Q;
cin >> Q;
for (int q = 0; q < Q; q) {
int l, r;
cin >> l >> r;
r;
cout << s[r] - s[l] << endl;
}
}
膜拜大神
代码语言：javascript复制#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please
const int cm = 1 << 17;
char cn[cm], *ci = cn cm, ct;
inline char getcha() {
if (ci - cn == cm) {
fread(cn, 1, cm, stdin);
ci = cn;
}
return *ci ;
}
inline int getint() {
int A = 0;
if (ci - cn 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 ct - '0';
else while ((ct = *ci ) >= '0') A = A * 10 ct - '0';
return A;
}
const int dm = 1 << 21;
char dn[dm], *di = dn;
inline void putint(int X) {
if (X == 0) {
*di = '0';
*di = 'n';
return;
}
int keta = 0;
char C[3];
while (X) {
*(C keta) = '0' X % 10;
X /= 10;
keta ;
}
for (int i = keta - 1; i >= 0; i--)*di = (*(C i));
*di = 'n';
}
int like[50001];
int main() {
//cin.tie(0);
//ios::sync_with_stdio(false);
int N = getint();
int like2017[672] = {2, 3, 7, 19, 31, 37, 79, 97, 139, 157, 199, 211, 229, 271, 307, 331, 337, 367, 379, 439, 499,
547, 577, 601, 607, 619, 661, 691, 727, 811, 829, 877, 937, 967, 997, 1009, 1069, 1171, 1237,
1279, 1297, 1399, 1429, 1459, 1531, 1609, 1627, 1657, 1759, 1867, 2011, 2029, 2089, 2131, 2137,
2179, 2221, 2281, 2311, 2467, 2539, 2551, 2557, 2617, 2707, 2719, 2791, 2851, 3019, 3037, 3061,
3067, 3109, 3169, 3181, 3187, 3319, 3331, 3391, 3499, 3529, 3607, 3697, 3709, 3739, 3769, 3877,
3967, 4027, 4051, 4111, 4159, 4177, 4231, 4261, 4339, 4357, 4447, 4507, 4567, 4591, 4621, 4639,
4801, 4831, 4861, 4909, 4951, 4987, 5167, 5179, 5227, 5419, 5431, 5479, 5557, 5581, 5659, 5749,
5839, 5851, 6037, 6079, 6121, 6151, 6211, 6217, 6229, 6271, 6277, 6301, 6361, 6379, 6421, 6427,
6547, 6691, 6709, 6841, 6961, 6967, 7219, 7297, 7369, 7411, 7507, 7537, 7561, 7621, 7639, 7681,
7687, 7867, 7951, 8017, 8167, 8191, 8209, 8287, 8317, 8329, 8461, 8521, 8527, 8539, 8629, 8647,
8689, 8941, 9007, 9049, 9067, 9091, 9109, 9127, 9151, 9157, 9199, 9241, 9277, 9319, 9397, 9619,
9721, 9739, 9859, 9901, 9907, 9931, 10177, 10267, 10321, 10429, 10501, 10531, 10597, 10639,
10657, 10789, 10831, 10837, 10909, 11047, 11251, 11287, 11311, 11497, 11527, 11587, 11779,
11839, 11887, 11959, 12049, 12211, 12241, 12391, 12421, 12517, 12577, 12619, 12781, 12829,
12967, 13009, 13147, 13159, 13219, 13249, 13411, 13417, 13441, 13477, 13537, 13627, 13669,
13681, 13729, 13999, 14029, 14149, 14197, 14407, 14419, 14461, 14551, 14737, 14821, 15091,
15121, 15259, 15277, 15289, 15319, 15331, 15349, 15391, 15427, 15541, 15619, 15661, 15667,
15679, 15739, 15787, 15937, 15991, 16087, 16189, 16249, 16267, 16417, 16519, 16651, 16729,
16747, 16879, 16981, 17029, 17107, 17137, 17191, 17257, 17449, 17491, 17659, 17761, 17839,
17989, 18049, 18121, 18217, 18229, 18397, 18439, 18451, 18457, 18637, 18661, 18679, 18787,
18859, 18979, 19141, 19231, 19417, 19477, 19489, 19609, 19687, 19699, 19867, 20047, 20089,
20107, 20347, 20407, 20509, 20611, 20641, 20707, 20809, 20947, 21031, 21169, 21187, 21397,
21481, 21559, 21589, 21601, 21661, 21787, 21799, 21817, 21859, 22027, 22051, 22111, 22129,
22147, 22447, 22531, 22669, 22717, 22741, 22777, 22807, 22921, 23011, 23071, 23131, 23431,
23497, 23509, 23581, 23677, 23761, 23767, 23827, 23857, 23869, 23899, 23929, 24061, 24097,
24169, 24337, 24379, 24391, 24517, 24631, 24697, 24709, 24799, 24841, 24979, 25111, 25171,
25189, 25411, 25447, 25579, 25609, 25621, 25741, 25759, 25819, 26029, 26041, 26119, 26161,
26227, 26251, 26407, 26431, 26479, 26539, 26557, 26641, 26701, 26959, 27061, 27067, 27091,
27109, 27211, 27259, 27271, 27337, 27361, 27487, 27529, 27691, 27751, 27817, 27919, 27961,
27967, 28027, 28051, 28057, 28099, 28201, 28219, 28351, 28387, 28411, 28429, 28447, 28537,
28549, 28597, 28621, 28687, 28729, 28927, 29077, 29209, 29221, 29269, 29287, 29347, 29527,
29599, 29611, 29641, 29671, 29917, 30109, 30169, 30187, 30319, 30367, 30469, 30529, 30577,
30631, 30649, 30781, 30829, 30841, 30859, 30931, 31069, 31237, 31249, 31267, 31327, 31387,
31657, 31699, 31771, 31849, 31891, 31957, 32077, 32119, 32191, 32257, 32359, 32587, 32647,
32707, 32719, 32749, 32779, 32839, 32941, 33151, 33181, 33301, 33349, 33427, 33487, 33529,
33577, 33637, 33739, 33769, 33871, 33889, 33967, 33997, 34057, 34141, 34261, 34369, 34501,
34537, 34729, 34747, 34849, 34939, 35059, 35089, 35149, 35251, 35311, 35461, 35491, 35617,
35671, 35677, 35797, 35911, 36037, 36241, 36307, 36451, 36469, 36571, 36709, 36739, 36781,
36847, 37039, 37159, 37189, 37357, 37507, 37567, 37591, 37861, 37897, 37957, 38167, 38281,
38299, 38377, 38569, 38821, 39079, 39097, 39139, 39439, 39451, 39667, 39679, 39769, 39829,
39847, 39901, 39937, 40039, 40087, 40111, 40237, 40351, 40357, 40459, 40507, 40591, 40759,
40819, 40927, 41011, 41077, 41131, 41281, 41491, 41539, 41611, 41617, 41719, 41809, 41851,
41887, 42061, 42157, 42337, 42349, 42397, 42457, 42649, 42667, 42727, 42859, 42967, 43177,
43207, 43591, 43627, 43669, 43711, 43717, 43759, 43777, 43987, 44059, 44089, 44119, 44131,
44257, 44371, 44449, 44497, 44647, 44917, 44959, 45061, 45541, 45691, 45697, 45757, 45979,
46021, 46279, 46381, 46411, 46447, 46471, 46549, 46567, 46747, 46819, 46957, 47017, 47059,
47137, 47161, 47221, 47287, 47389, 47419, 47497, 47629, 47659, 47701, 47791, 47809, 47857,
47869, 48049, 48079, 48091, 48247, 48259, 48487, 48541, 48589, 48751, 48781, 48889, 48907,
49009, 49369, 49477, 49639, 49789, 49831, 49939};
rep(i, 672)
like[like2017[i]] = 1;
rep(i, 50000)
like[i 1] = like[i];
rep(i, N)
{
int l = getint() >> 1, r = getint() >> 1;
putint(like[r 1] - like[l]);
}
fwrite(dn, 1, di - dn, stdout);
Would you please return 0;
}
