TS10 Quảng Ngãi 2026 - Bài 3
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Cho hai số nguyên dương ~n, k~ và dãy số gồm ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~.
Yêu cầu: Tính số lượng cặp ~(i, j)~ thỏa mãn ~(1 \le i < j \le n)~ sao cho tích ~a_i \times a_j~ chia hết cho ~k~.
Input
Dòng thứ nhất chứa hai số nguyên dương lần lượt là ~n, k~ ~(1 \le n, k \le 10^5)~.
Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^9, 1 \le i \le n)~.
Output
Một số nguyên là kết quả thỏa mãn yêu cầu bài toán.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~60\%~ | ~n \le 10^3, k \le 10^3~ |
| 2 | ~40\%~ | ~n \le 10^5, k \le 10^5~ |
Sample Input 1
5 4
3 2 6 3 2
Sample Output 1
3
Notes
Có ~3~ cặp thỏa mãn đề bài là:
Cặp ~(2, 3)~ có ~a_2 \times a_3 = 2 \times 6 = 12~ chia hết cho ~4~.
Cặp ~(2, 5)~ có ~a_2 \times a_5 = 2 \times 2 = 4~ chia hết cho ~4~.
Cặp ~(3, 5)~ có ~a_3 \times a_5 = 6 \times 2 = 12~ chia hết cho ~4~.
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.