Bộ ba số

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

Thời gian: 1.5s

Bộ nhớ: 64M

Input: bàn phím

Output: màn hình

Tác giả:

huyhau6a2

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)$ ( $i<j<k$ ) mà $a_i\cdot a_j\cdot a_k$ chia hết cho $m$

Input, Output và Subtasks

Input

Dòng đầu tiên chứa 2 số nguyên $n$ và $m$ ( $3\le n\le 10^5,1\le m\le 10^9$ )
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

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

Subtasks

Subtask 1 $(25\%)$ : $n\le 200$
Subtask 2 $(25\%)$ : $n\le 2000$
Subtask 3 $(25\%)$ : $n\le 10^4$
Subtask 4 $(25\%)$ : Không có ràng buộc gì thêm

Sample 1

Input

5 6
2 3 1 2 2

Output

Note

Có 6 bộ ba $(i,j,k)$ thỏa mãn là $(1,2,3), (1,2,4), (1,2,5), (2,3,4), (2,3,5), (2,4,5)$

Sample 2

Input

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

Output

Note

Có tất cả 85 bộ ba số $(i,j,k)$ thỏa mãn chia hết cho $3$

Bình luận

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