Bộ ba số (THTB ĐN 2023)

Điểm: 1300 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: BOBASO.inp

Output: BOBASO.out

Tác giả:

Sunlight

Dạng bài

Cho $n$ số nguyên không âm $a_1,a_2,\dots,a_n$ và một số nguyên dương $m$ . Hãy đếm số bộ ba số $(i,j,k)$ mà $a_i\cdot a_j\cdot a_k$ chia hết cho $m$ (lưu ý nếu 2 bộ ba mà bộ này là hoán vị của bộ kia thì vẫn tính là 2 bộ, ví dụ $(1,2,3)$ và $(2,1,3)$ là hai bộ khác nhau)

Input, Output và Subtasks

Input: (BOBASO.inp)

Dòng đầu tiên chứa 2 số nguyên $n$ và $m$ ( $1\le n\le 2\cdot 10^3,1\le m\le 3\cdot 10^3$ )
Dòng thứ hai chứa $n$ số nguyên không âm $a_1,a_2,\dots,a_n$ ( $0\le a_i\le 10^9$ )

Output: (BOBASO.out)

Số nguyên duy nhất là số bộ ba số thỏa mãn yêu cầu

Subtasks

Subtask 1 $(50\%)$ : $n\le 200$
Subtask 2 $(50\%)$ : Không có ràng buộc gì thêm

Sample 1

Input (BOBASO.inp)

2 5
1 5

Output (BOBASO.out)

Note

Có 7 bộ ba là $(1,1,5), (1,5,1), (1,5,5), (5,1,1), (5,1,5), (5,5,1), (5,5,5)$

Sample 2

Input (BOBASO.inp)

10 3
1 2 3 4 5 6 7 8 9 10

Output (BOBASO.out)

Note

Có tất cả 657 bộ ba số thỏa mãn chia hết cho $3$

Bình luận

Không có bình luận nào.