Geometric Progression

题意翻译

## 题目描述 Polycarp只有三岁，他只喜欢长度为三。他还有一个最喜欢的整数k和一个序列a，a是由n个整数组成的。 他想知道从a中可以选择多少个长度为3的子序列，这样它们就形成了一个具有公共比值k的几何级数。 长度3的子序列是这三个指数i1,i2,i3,1<=i1<i2<i3<=n.这些元素在序列中不一定连续，但它们是递增的。 公比k的几何级数形式为b·k^0、b·k^1、…、b·k^r-1。 ## 输入格式 输入的第一行包含两个整数，n和k（1<=N，K<=2·10^5)表示Polycarp的序列有多少个数字和他最喜欢的数字. 第二行包含n个整数,a1,a2,...,an(-10^9<=ai<=10^9). ## 输出格式 输出一个数字---选择长度为3的子序列的方法的数目，这样它就形成了一个公共比率k的几何级数。

题目描述

Polycarp loves geometric progressions very much. Since he was only three years old, he loves only the progressions of length three. He also has a favorite integer $ k $ and a sequence $ a $ , consisting of $ n $ integers. He wants to know how many subsequences of length three can be selected from $ a $ , so that they form a geometric progression with common ratio $ k $ . A subsequence of length three is a combination of three such indexes $ i_{1},i_{2},i_{3} $ , that $ 1<=i_{1}&lt;i_{2}&lt;i_{3}<=n $ . That is, a subsequence of length three are such groups of three elements that are not necessarily consecutive in the sequence, but their indexes are strictly increasing. A geometric progression with common ratio $ k $ is a sequence of numbers of the form $ b·k^{0},b·k^{1},...,b·k^{r-1} $ . Polycarp is only three years old, so he can not calculate this number himself. Help him to do it.

输入输出格式

输入格式

The first line of the input contains two integers, $ n $ and $ k $ ( $ 1<=n,k<=2·10^{5} $ ), showing how many numbers Polycarp's sequence has and his favorite number. The second line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ -10^{9}<=a_{i}<=10^{9} $ ) — elements of the sequence.

输出格式

Output a single number — the number of ways to choose a subsequence of length three, such that it forms a geometric progression with a common ratio $ k $ .

输入输出样例

输入样例 #1

5 2
1 1 2 2 4

输出样例 #1

4

输入样例 #2

3 1
1 1 1

输出样例 #2

1

输入样例 #3

10 3
1 2 6 2 3 6 9 18 3 9

输出样例 #3

6

说明

In the first sample test the answer is four, as any of the two 1s can be chosen as the first element, the second element can be any of the 2s, and the third element of the subsequence must be equal to 4.