Olympic chuyên KHTN 2025 - COPRIME

Xem dạng PDF

Gửi bài giải

Điểm: 17,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Định nghĩa dãy ~a~ gồm ~n~ phần tử là dãy đẹp khi ước chung lớn nhất của mọi cặp ~(a_i, a_j)~ bằng ~1~ với mọi ~i \ne j~ và ~a_i~ lớn hơn ~1~ với mọi ~i~.

Cho số ~n~, tìm tổng nhỏ nhất của dãy đẹp có ~n~ phần tử.

Input

Gồm ~1~ số duy nhất ~n~ ~(n \le 10^6)~ là độ dài của dãy đẹp cần tìm.

Output

Gồm ~1~ số duy nhất là tổng nhỏ nhất của dãy đẹp tìm được.

Scoring

Subtask Điểm Ràng buộc
1 ~10\%~ ~n \le 10~
2 ~30\%~ ~n \le 10^3~
3 ~60\%~ ~n \le 10^6~

Sample Input 1

1

Sample Output 1

2

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 0
    missmphuog  đã bình luận lúc 1, Tháng 11, 2026, 16:19
    #include <bits/stdc++.h>
    using namespace std;
    
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    
        int n;
        cin >> n;
    
        int limit = 16;
    
        while (true) {
            vector<bool> prime(limit + 1, true);
            prime[0] = prime[1] = false;
    
            for (int i = 2; 1LL * i * i <= limit; ++i) {
                if (prime[i]) {
                    for (long long j = 1LL * i * i;
                         j <= limit; j += i) {
                        prime[j] = false;
                    }
                }
            }
    
            int cnt = 0;
            long long sum = 0;
    
            for (int i = 2; i <= limit; ++i) {
                if (prime[i]) {
                    sum += i;
                    ++cnt;
    
                    if (cnt == n) {
                        cout << sum << '\n';
                        return 0;
                    }
                }
            }
    
            limit *= 2;
        }
    }