Bài 3 (4,0 điểm; Đề TS vào 10 - Quảng Ngãi 2026 - 2027)

Cho hai số nguyên dương n, k và dãy số gồm n số nguyên dương a₁, a₂, ..., a_n.
Yêu cầu: Tính số lượng cặp (i, j) thỏa mãn (1 ≤ i < j ≤ n) sao cho tích a_i × a_j chia hết cho k.

Dữ liệu vào: Từ tệp văn bản BAI3.INP có cấu trúc:

• Dòng thứ nhất chứa hai số nguyên dương lần lượt là n, k (1 ≤ n, k ≤ 10⁵).
• Dòng thứ hai chứa n số nguyên dương a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹, 1 ≤ i ≤ n). Các số trên cùng một dòng cách nhau bởi dấu cách.

Dữ liệu ra: Ghi ra tệp văn bản BAI3.OUT có cấu trúc:

• Ghi một số nguyên là kết quả thỏa mãn yêu cầu bài toán.

Ví dụ:

Giới hạn:

• Subtask 1 (60% số điểm): Có 60% test với n ≤ 10³, k ≤ 10³.
• Subtask 2 (40% số điểm): Có 40% test với n ≤ 10⁵, k ≤ 10⁵.