Hướng giải: Với mỗi thao tác, ta đếm số các số thuộc tập $S$ nguyên tố cùng nhau với $x$ rồi cập nhật đáp án.

Subtask 1

Ta dùng cấu trúc dữ liệu unordered_multiset của C++ để biểu diễn tập $S$. Với mỗi thao tác, duyệt qua từng số thuộc tập $S$ rồi kiểm tra số đó có nguyên tố cùng nhau với $x$ không.

Độ phức tạp: $O(q^2)$

Subtask 2

Phân tích $x$ thành thừa số nguyên tố: $x$ = $p_1^{a_1}{p}_2^{a_2}...p_n^{a_n}$

Theo nguyên lí bao hàm - loại trừ${}^1$, số các số thuộc tập $S$ nguyên tố cùng nhau với $x$ là:

+ Số các số thuộc tập $S$

- Số các số thuộc tập $S$ chia hết cho $p_1$

- Số các số thuộc tập $S$ chia hết cho $p_2$

- Số các số thuộc tập $S$ chia hết cho $p_3$

...

+ Số các số thuộc tập $S$ chia hết cho $p_1$ và $p_2$

+ Số các số thuộc tập S chia hết cho $p_1$ và $p_3$

+ Số các số thuộc tập $S$ chia hết cho $p_2$ và $p_3$

...

Vì $x\le {10}^6$ nên $x$ có tối đa $8$ ước số nguyên tố khác nhau (chứng minh bằng cách tính tích $2\ast 3\ast 5·...$). Ta dùng bitmask để tính giá trị trên trong $O(2^8)$.

Gọi $cnt[k]$ là số các số thuộc tập $S$ chia hết cho $k$. Vì ta chỉ quan tâm đến các giá trị $k$ không có ước chính phương khác $1$ nên ta không cần duyệt qua tất cả các ước của $x$ để cập nhật $cnt$. Ta cập nhật $cnt$ ngay trong lúc duyệt bitmask.

Chi tiết cách cài đặt các bạn có thể xem code mẫu.

Độ phức tạp: $O(q\ast \sqrt{MAXX}+q\ast 2^8)$

${}^1$Đọc thêm về nguyên lí bao hàm - loại trừ tại https://cp-algorithms.com/combinatorics/inclusion-exclusion.html