【小码匠自习室】ABC084 - D：喜欢这样的大神，超有才华

小码匠

发布于 2022-08-08 13:17:42

2270

发布于 2022-08-08 13:17:42

碎碎念

灵异事件：第七行的灵异事件，导致在执行模式执行cout能不输出结果，在debug模式执行cout能输出结果

    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的大神，结果点进去竟然是打表！！！世界崩塌的感觉，重点是，这还是个初段大神啊！！！初段诶！

    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:

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

1
3 7

Sample Output 1

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

Sample Output 2

Note that 2017 is also similar to 2017.

Sample Input 3

Sample Output 3

题解

小码匠题解

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;
    }
}

参考题解

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;
    }
}

膜拜大神

#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;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2022-06-28，如有侵权请联系 cloudcommunity@tencent.com 删除

cout