* Sàng nguyên tố Eratosthenes (Sieve of Eratosthenes)

Hướng tiếp cận Ban đầu, ta cho tất cả các số từ 2 đến n vào sàng và đánh dấu tất cả các số. (Các số không được đánh dấu sau cùng sẽ bị loại khỏi sàng). Duyệt lần lượt các số từ 2 đến n. Nếu số đang xét:

Đã được đánh dấu

⇒ số nguyên tố: ta bỏ đánh dấu tất cả các bội (khác chính nó) của số nguyên tố này để loại các bội ấy ra khỏi sàng.

Không được đánh dấu

⇒ hợp số: ta bỏ qua số này. Sau khi duyệt xong, các số còn lại trong sàng, hay nói cách khác các số được đánh dấu là số nguyên tố.

Ta có thể hiểu như hình dưới đây:

Code C++ minh họa

const int maxn = 1000000 + 5; //10^6 + 5
bool is_prime[maxn]; // mảng bool khởi tạo với các giá trị false  
void sieve(int n){
    // Đánh dấu các số từ 2 đến n đều là số nguyên tố
    for (int i = 2; i <= n; i++)
        is_prime[i] = true;
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i * 2; j <= n; j += i)
            // Bỏ đánh dấu tất cả các số không phải số nguyên tố
                is_prime[j] = false;
        }
    }
}

Độ phức tạp thời gian là O(n*(1/2+1/3+...+1/p) với p là số nguyên tố <= n.

Độ phức tạp thời gian là O(n log log n)

Đô phức tạp không gian là O(n)

Dựa vào Nhận xét trên, ta có cải tiến như sau:

CODE MẪU :

const int maxn = 1000000 + 5; //10^6 + 5
bool is_prime[maxn];
void Eratosthenes(int n){
    for (int i = 2; i <= n; i++)
        is_prime[i] = true;
    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            // j sẽ bắt đầu chạy từ i * i
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = false;
        }
    }
}

Độ phức tạp thời gian vẫn vậy.Tuy nhiên, số phép tính đã giảm đi đáng kể.

>> link hướng dẫn chi tiết về sàng nguyên tố

(em xin phep de tieng anh vi em ko bat telex duoc) many month ago, i have making a huge mess by making a war and disrespect everyone in the discord server today, i am very regret of my behaviour and want to sorry everyone:

• sorry to the moderator of my bad behaviour
• sorry to kuroni and lekienthanh for ragebaiting them( even if i don't mean like that) I can't control everyone but i hope no one will get offended by my mistake and hope that everyone will forgive me, even it is late to say

🚀 CP-Algorithms Tiếng Việt: Phá Bỏ Rào Cản Ngôn Ngữ Trong Lập Trình Thi Đấu

Nếu bạn là một người đam mê thuật toán, chắc hẳn cái tên e-maxx hay CP-Algorithms đã quá quen thuộc. Đây là kho tàng kiến thức đồ sộ, nơi chứa đựng mọi thứ từ những thuật toán cơ bản đến những cấu trúc dữ liệu nâng cao nhất.

Tuy nhiên, việc tiếp cận bằng tiếng Anh đôi khi là một trở ngại lớn khiến nhiều bạn trẻ Việt Nam khó tiếp thu trọn vẹn tinh túy của bài viết. Đó chính là lý do dự án CP-Algorithms Tiếng Việt ra đời!

🌟 Tại sao bạn không nên bỏ lỡ trang web này?

Dự án không chỉ đơn thuần là dịch thuật, mà còn là nỗ lực mang lại trải nghiệm học tập gần gũi nhất cho cộng đồng Coder Việt:

• Nội dung chuẩn xác: Các thuật toán được chuyển ngữ tỉ mỉ, giữ đúng thuật ngữ chuyên ngành nhưng vẫn đảm bảo sự dễ hiểu.
• Đầy đủ mã nguồn: Giữ nguyên các đoạn code mẫu tối ưu, giúp bạn có thể thực hành ngay lập tức.
• Hoàn toàn miễn phí: Truy cập mọi lúc, mọi nơi trên nền tảng GitHub Pages mượt mà.

📚 Bạn sẽ học được gì?

Từ những bước chân đầu tiên cho đến khi chinh phục các kỳ thi Olympic (VOI) hay kỳ thi quốc tế (ICPC), trang web bao hàm tất cả:

🤝 Cùng nhau xây dựng cộng đồng

Đây là một dự án mở. Nếu bạn yêu thích thuật toán và muốn đóng góp cho cộng đồng, bạn hoàn toàn có thể tham gia hiệu đính hoặc dịch các bài viết mới. Mỗi đóng góp của bạn đều giúp lộ trình học tập của các thế hệ Coder Việt sau này trở nên bằng phẳng hơn.

Ghé thăm ngay tại: https://deanqkhanhcoder.github.io/cp-algorithms-vi/

Hãy chia sẻ bài viết này đến bạn bè và cùng nhau nâng tầm tư duy thuật toán của người Việt nhé! 🔥

include <bits></bits>

using namespace std;

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

int N, K;
cin >> N >> K;
vector<long long> a(N);
for(int i = 0; i < N; i++) cin >> a[i];

unordered_map<long long, vector<int>> pos;
pos.reserve(N * 2);

for(int i = 0; i < N; i++)
    pos[a[i]].push_back(i + 1);

long long ans = 0;

for(auto &p : pos){
    auto &v = p.second;
    int t = v.size();
    if(t < K) continue;

    for(int i = 0; i + K - 1 < t; i++){
        for(int j = i + K - 1; j < t; j++){
            int c = j - i + 1;
            int maxLen = 2 * c - 1;

            int Lmin = v[j] - maxLen + 1;
            int Lmax = v[i];

            int Rmin = v[j];
            int Rmax = v[i] + maxLen - 1;

            Lmin = max(Lmin, 1);
            Lmax = min(Lmax, v[i]);

            Rmin = max(Rmin, v[j]);
            Rmax = min(Rmax, N);

            if(Lmin > Lmax || Rmin > Rmax) continue;

            long long total = 1LL * (Lmax - Lmin + 1) * (Rmax - Rmin + 1);
            ans += total;
        }
    }
}

cout << ans;

}

Cho mảng gồm 𝑁 N số nguyên dương 𝐴 1 , 𝐴 2 , … , 𝐴 𝑁 A 1 ​

,A 2 ​

,…,A N ​

và một số nguyên 𝐾 K.

Một đoạn con liên tiếp [ 𝐿 , 𝑅 ] [L,R] được gọi là K-dominant nếu tồn tại một giá trị 𝑋 X sao cho:

số lần xuất hiện của 𝑋 X trong đoạn lớn hơn tổng số lần xuất hiện của tất cả các giá trị khác trong đoạn (tức là 𝑓 𝑟 𝑒 𝑞 ( 𝑋 ) > ( 𝑅 − 𝐿 + 1 ) − 𝑓 𝑟 𝑒 𝑞 ( 𝑋 ) freq(X)>(R−L+1)−freq(X))

và đồng thời 𝑓 𝑟 𝑒 𝑞 ( 𝑋 ) ≥ 𝐾 freq(X)≥K.

Hãy đếm số lượng đoạn con K-dominant.

Ràng buộc:

1 ≤ 𝑁 ≤ 2 × 10 5 1≤N≤2×10 5

1 ≤ 𝐴 𝑖 ≤ 10 9 1≤A i ​

≤10 9

1 ≤ 𝐾 ≤ 𝑁 1≤K≤N

Input:

N K A1 A2 ... AN

Output: In ra một số nguyên là số đoạn con K-dominant.

Ví dụ:

Input 6 2 1 2 2 2 3 2

Output 7