407969: GYM102953 6 Favorite Product

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

6. Favorite Producttime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You have an array $$$a$$$ consisting of $$$n$$$ integers. Your favorite number is $$$k$$$, and you want to see if you can find any triple of distinct indices with a product of $$$k$$$. In other words, you're looking for three distinct indices $$$x$$$, $$$y$$$, and $$$z$$$, such that $$$a_x * a_y * a_z = k$$$.

Input

The first line of input contains two space separated integers $$$n$$$ $$$(1 <= n <= 10^5)$$$ and $$$k$$$ $$$(1 <= k <= 10^5)$$$.

The next line consists of $$$n$$$ space-separated integers: the array $$$a$$$ $$$(1 <= a_i <= 10^4)$$$.

Output

Output a single positive integer representing the number of triples of distinct indices in $$$a$$$ that have a product of $$$k$$$.

Scoring

Subtask 1 (4 points): $$$n <= 100$$$

Subtask 2 (8 points): $$$n <= 2000$$$

Subtask 3 (26 points): no additional constraints

ExamplesInput
5 24
6 2 3 4 1
Output
2
Input
7 7
1 1 1 7 7 7 8
Output
9
Input
6 27
1 3 3 3 3 9
Output
8

加入题单

上一题 下一题 算法标签: