Tutorial — Đếm Số Cực Tốt

Số lượng các số thỏa mãn định nghĩa số cực tốt trong miền giá trị bài toán là rất nhỏ.

Việc đếm số lượng phần tử thỏa mãn trong một đoạn $[u, v]$ có thể quy về hiệu hai giá trị tích lũy từ đầu dãy đến $v$ và từ đầu dãy đến $u - 1$.

Sử dụng thuật toán quay lui xuất phát từ các chữ số nguyên tố ban đầu để sinh toàn bộ tập hợp các số cực tốt.

Tiền xử lý tập hợp số cực tốt bằng quay lui, sau đó dựng mảng cộng dồn trên dãy ban đầu để trả lời mỗi truy vấn trong $O(1)$.