Codeforces Round #Pi (Div. 2) |
---|
Закончено |
Поликарп очень любит геометрические прогрессии. Так как ему только три года, он любит прогрессии только длины три. Также у него есть любимое целое число k и последовательность a, состоящая из n целых чисел.
Он хочет узнать: сколько подпоследовательностей длины три можно выбрать из a так, чтобы они образовывали геометрическую прогрессию со знаменателем k.
Подпоследовательностью длины три называются три таких индекса i1, i2, i3, что 1 ≤ i1 < i2 < i3 ≤ n. То есть подпоследовательности длины три — это такие тройки элементов, которые необязательно идут подряд в последовательности, но их индексы строго возрастают.
Геометрическая прогрессия со знаменателем k — это последовательность чисел вида b·k0, b·k1, ..., b·kr - 1.
Поликарпу всё ещё три года, поэтому он не может посчитать это количество самостоятельно. Помогите ему сделать это.
В первой строке входных данных содержится два целых числа n и k (1 ≤ n, k ≤ 2·105) — количество чисел в последовательности Поликарпа и его любимое число.
Вторая строка содержит n целых чисел a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — элементы последовательности.
Выведите единственное число — количество способов выбрать такую подпоследовательность длины три, что она образует геометрическую прогрессию со знаменателем k.
5 2
1 1 2 2 4
4
3 1
1 1 1
1
10 3
1 2 6 2 3 6 9 18 3 9
6
В первом примере ответ четыре, так как в качестве первого элемента можно выбрать любую из двух единиц, в качестве второго — любую из двух двоек, а третий элемент подпоследовательности обязательно должен равняться четырём.
Название |
---|