Phân tích

Bài toán mô tả một quá trình nhóm các số nguyên vào các tập hợp, sau đó yêu cầu chúng ta đếm số lượng tập hợp cuối cùng.

Quá trình được mô tả trong đề bài khá chậm:

1. Tạo các tập hợp rời rạc cho từng số nguyên.
2. Xét từng cặp số nguyên.
3. Phân tích thừa số nguyên tố của hai số và kiểm tra xem chúng có ước nguyên tố chung nào lớn hơn hoặc bằng \(P\) hay không.
4. Nếu có, hợp nhất các tập hợp chứa hai số đó.

Chúng ta cần tìm kết quả của quá trình này bằng một phương pháp nhanh hơn. Một vài quan sát dưới đây sẽ giúp ích:

Thứ nhất, chúng ta chỉ cần tìm các ước nguyên tố nhỏ hơn kích thước của khoảng (số phần tử là \(B - A + 1\)). Nếu một số nguyên tố lớn hơn hoặc bằng kích thước của khoảng, thì trong khoảng đó có tối đa một số nguyên chia hết cho số nguyên tố đó, vì vậy nó sẽ không bao giờ được dùng để hợp nhất các tập hợp.

Thứ hai, chúng ta có thể tiếp cận nhanh hơn việc phân tích thừa số nguyên tố của từng số riêng biệt. Thay vào đó, chúng ta xem xét từng số nguyên tố và tìm tất cả các số nguyên trong khoảng chia hết cho số nguyên tố đó, một kỹ thuật thường được gọi là sàng (sieve).

Thứ ba, việc hợp nhất các tập hợp có thể được thực hiện hiệu quả bằng cấu trúc dữ liệu Union-Find (hay còn gọi là cấu trúc dữ liệu các tập hợp rời rạc). Khi xét mỗi số nguyên tố và tìm thấy tất cả các số nguyên chia hết cho nó, chúng ta hợp nhất tất cả các tập hợp chứa các số nguyên đó lại. Chúng ta cũng có thể coi đây là bài toán tìm các thành phần liên thông trong một đồ thị vô hướng, với các nút là các số nguyên trong khoảng và các số nguyên tố, và các cạnh nối giữa một số nguyên với các ước nguyên tố của nó.

Cách cài đặt

1. Sử dụng thuật toán Sàng Eratosthenes để tìm tất cả các số nguyên tố lên đến \(B - A\) (hoặc lên đến một giới hạn an toàn như \(10^6\)).
2. Khởi tạo cấu trúc Union-Find cho các số từ \(A\) đến \(B\). Có tổng cộng \(B - A + 1\) phần tử.
3. Với mỗi số nguyên tố \(q \ge P\):
   • Tìm số nguyên đầu tiên \(i\) trong khoảng \([A, B]\) mà \(i\) chia hết cho \(q\). Số này có thể tìm được bằng công thức: \(i = \lceil A/q \rceil \times q\).
   • Duyệt qua tất cả các số \(j = i + q, i + 2q, \dots\) sao cho \(j \le B\).
   • Hợp nhất (Union) tất cả các số \(i, i+q, i+2q, \dots\) vào cùng một tập hợp trong cấu trúc Union-Find.
4. Đếm số lượng các đại diện (root) khác nhau trong Union-Find để đưa ra kết quả cuối cùng.

Độ phức tạp

• Việc tìm các số nguyên tố tốn khoảng \(O(N \log \log N)\) với \(N = B - A\).
• Việc duyệt qua các bội số của các số nguyên tố trong khoảng tương tự như thuật toán sàng, tốn khoảng \(O(N \log \log N)\).
• Các thao tác Union-Find tốn thời gian gần như hằng số \(O(\alpha(N))\).
• Tổng độ phức tạp là \(O(N \log \log N)\), với \(N = B - A \le 10^6\).

Dựa trên phân tích chính thức của Google Code Jam.