Link đến bài COPRIME - Nguyên tố cùng nhau
Trước hết cần chú ý:
- Nếu tập có những số trùng nhau thì ta chỉ giữ lại một trong số đó;
- Nếu tập có thì ta chỉ cần giữ lại ; Từ đó có thể thấy nếu các phần tử của tập không vượt quá thì tập có không quá phần tử.
Subtask 1:
Với tập không quá phần tử ta có thể xét tất cả các khả năng chọn một tập con của (có cách chọn)
Subtask 2:
Với tập có không quá phần tử và các phần tử .
Trước hết ta có nhận xét:
- Nếu và có ước nguyên tố thì là số nguyên tố, do đó ta có thể lấy được số đó (và loại khỏi tập ). Từ đó chỉ cần xét tập gồm các số có ước nguyên tố thuộc tập .
Thuật toán QHĐ trạng thái:
- Ta đánh số thứ tự các số nguyên tố từ đến (có số nguyên tố tất cả theo danh sách trên)
- Gọi là số phần tử nhiều nhất của tập con của khi xét đến phần tử thứ và chỉ lấy các số có ước nguyên tố là các chỉ số bit trong biểu diễn nhị phân của . Ví dụ là số phần tử nhiều nhất của tập con khi xét đến phần tử thứ của và chỉ lấy các số có ước nguyên tố là và (do có biểu diễn nhị phân là ) (phần còn lại là phần của các bạn :) )