Hướng dẫn cho Bedan Contest #02 - A - Đếm số chia hết

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: flo

Subtask $1$ : $1 \le n, q \le 2 \times 10^{3}$ .

Hint

Cày trâu chứ còn cái gì :D

Solution

Với mỗi truy vấn, ta sẽ duyệt qua đoạn $[l, r]$ và đếm số lượng số mà $m$ chia hết.
Độ phức tạp của ý tưởng trên là $O(q \times (r-l+1)$ ).

Subtask $2$ : Không giới hạn gì thêm.

Hint

Những số mà $m$ chia hết là ước của $m$ .

Solution

Từ gợi ý trên, ta sẽ duyệt qua các ước của $m$ và với mỗi ước, ta sẽ đếm số lần xuất hiện của nó trong đoạn $[l, r]$ .
Để đếm số lần xuất hiện của $x$ trong đoạn $[l, r]$ thì đầu tiên, ta sẽ lưu lại vị trí của $x$ trong dãy $a$ vào $1$ mảng. Sau đó với mỗi đoạn $[l, r]$ , ta sẽ sử dụng chặt nhị phân trên mảng lưu vị trí của $x$ . Việc lưu lại vị trí sẽ được thực hiện trước và trên các phần tử của dãy $a$ .
Để dễ hình dung ý tưởng trên, với dãy $a = [1, 2, 4, 3, 2]$ thì ta sẽ có một mảng lưu vị trí là $[1: [1], 2: [2, 5], 3: [4], 4: [3]]$ .
Độ phức tạp của ý tưởng trên là $O(q \times \sqrt{m} \times (log_2l+log_2r)$ .

Câu hỏi

Bạn có thể giải bài này bằng Chia Căn không.

Bình luận

Không có bình luận nào.