(cache)Submission #67154357 - AtCoder Beginner Contest 412

Contest Duration: 2025-06-28(Sat) 21:00 - 2025-06-28(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #67154357

Source Code Expand

Copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<bool> segmented_sieve(ll L, ll R) {
    ll lim = floor(sqrt(R)) + 1;
    vector<bool> is_prime_small(lim+1, true);
    vector<bool> is_prime(R-L+1, true);
    is_prime_small[0] = is_prime_small[1] = false;
    for (ll i = 2; i <= lim; ++i) {
        if (!is_prime_small[i]) continue;
        for (ll j = i*i; j <= lim; j += i) is_prime_small[j] = false;
        ll start = max(i*i, ((L + i - 1) / i) * i);
        for (ll j = start; j <= R; j += i) {
            is_prime[j - L] = false;
        }
    }
    if (L == 1) is_prime[0] = false;  // 1 は素数でない
    return is_prime;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<bool> segmented_sieve(ll L, ll R) {
    ll lim = floor(sqrt(R)) + 1;
    vector<bool> is_prime_small(lim+1, true);
    vector<bool> is_prime(R-L+1, true);
    is_prime_small[0] = is_prime_small[1] = false;
    for (ll i = 2; i <= lim; ++i) {
        if (!is_prime_small[i]) continue;
        for (ll j = i*i; j <= lim; j += i) is_prime_small[j] = false;
        ll start = max(i*i, ((L + i - 1) / i) * i);
        for (ll j = start; j <= R; j += i) {
            is_prime[j - L] = false;
        }
    }
    if (L == 1) is_prime[0] = false;  // 1 は素数でない
    return is_prime;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll L, R;
    cin >> L >> R;

    auto is_prime = segmented_sieve(L+1, R);
    ll cnt_primes = 0;
    for (bool v : is_prime) if (v) ++cnt_primes;

    ll lim = floor(sqrt(R)) + 1;
    vector<bool> is_small_prime(lim+1, true);
    is_small_prime[0] = is_small_prime[1] = false;
    for (ll i = 2; i*i <= lim; ++i) {
        if (!is_small_prime[i]) continue;
        for (ll j = i*i; j <= lim; j += i) is_small_prime[j] = false;
    }
    vector<ll> small_primes;
    for (ll i = 2; i <= lim; ++i) {
        if (is_small_prime[i]) small_primes.push_back(i);
    }

    unordered_set<ll> set_pp;  
    for (ll p : small_primes) {
        __int128 cur = (__int128)p * p;  
        while (cur <= R) {
            if (cur > L) set_pp.insert((ll)cur);
            cur *= p;
        }
    }
    ll cnt_pp = set_pp.size();

    ll answer = 1 + cnt_primes + cnt_pp;
    cout << answer << "\n";
    return 0;
}

Submission Info

Submission Time	2025-06-28 22:07:08
Task	E - LCM Sequence
User	bhtri
Language	C++ 23 (gcc 12.2)
Score	500
Code Size	1696 Byte
Status	AC
Exec Time	167 ms
Memory	15928 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

500 / 500

Status

× 3

× 31

Set Name	Test Cases
Sample	00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All	00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_1_00.txt, 01_random_1_01.txt, 01_random_1_02.txt, 01_random_1_03.txt, 01_random_1_04.txt, 01_random_1_05.txt, 01_random_1_06.txt, 01_random_1_07.txt, 01_random_1_08.txt, 01_random_1_09.txt, 02_random_2_00.txt, 02_random_2_01.txt, 02_random_2_02.txt, 02_random_2_03.txt, 02_random_2_04.txt, 02_random_2_05.txt, 02_random_2_06.txt, 02_random_2_07.txt, 02_random_2_08.txt, 02_random_2_09.txt, 02_random_2_10.txt, 02_random_2_11.txt, 02_random_2_12.txt, 02_random_2_13.txt, 02_random_2_14.txt, 03_corner_00.txt, 03_corner_01.txt, 03_corner_02.txt

Case Name	Status	Exec Time	Memory
00_sample_00.txt	AC	1 ms	3532 KiB
00_sample_01.txt	AC	1 ms	3688 KiB
00_sample_02.txt	AC	167 ms	15928 KiB
01_random_1_00.txt	AC	155 ms	15640 KiB
01_random_1_01.txt	AC	122 ms	10184 KiB
01_random_1_02.txt	AC	41 ms	4792 KiB
01_random_1_03.txt	AC	56 ms	6528 KiB
01_random_1_04.txt	AC	165 ms	15796 KiB
01_random_1_05.txt	AC	107 ms	12876 KiB
01_random_1_06.txt	AC	112 ms	9808 KiB
01_random_1_07.txt	AC	47 ms	6316 KiB
01_random_1_08.txt	AC	132 ms	15136 KiB
01_random_1_09.txt	AC	60 ms	6440 KiB
02_random_2_00.txt	AC	72 ms	5596 KiB
02_random_2_01.txt	AC	72 ms	5692 KiB
02_random_2_02.txt	AC	71 ms	5656 KiB
02_random_2_03.txt	AC	95 ms	7308 KiB
02_random_2_04.txt	AC	95 ms	7264 KiB
02_random_2_05.txt	AC	96 ms	7300 KiB
02_random_2_06.txt	AC	63 ms	5084 KiB
02_random_2_07.txt	AC	63 ms	5052 KiB
02_random_2_08.txt	AC	63 ms	5048 KiB
02_random_2_09.txt	AC	145 ms	14492 KiB
02_random_2_10.txt	AC	144 ms	14436 KiB
02_random_2_11.txt	AC	143 ms	14628 KiB
02_random_2_12.txt	AC	119 ms	10140 KiB
02_random_2_13.txt	AC	119 ms	10116 KiB
02_random_2_14.txt	AC	119 ms	10116 KiB
03_corner_00.txt	AC	1 ms	3472 KiB
03_corner_01.txt	AC	44 ms	4376 KiB
03_corner_02.txt	AC	4 ms	3624 KiB