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 ≤ 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*3*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 *\sqrt{MAXX} + q * 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