Problem D: [Median II] Two-Product

Problem D: [Median II] Two-Product

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1738  Solved: 207
[Submit][Status][Web Board]


Neko thinks the two-sum problem is easy for you, so he tests you by a new problem —— the two-product problem.

Given an array of integers, \(a_1, a_2, a_3, ... , a_N\), and an integer \(M\). Please output the number of pairs \((a_i,a_j),i< j\), such that \(a_i * a_j=M\).


The first line contains a single integer \(N(1{\leq}N{\leq}10^6)\) —— the length of the array.

The second line contains a single integer \(M(-10^{18}{\leq}M{\leq}10^{18})\) —— the specific target.

The third line contains \(N\) integers \(a_1, a_2, a_3, ... , a_N(-10^9{\leq}a_i{\leq}10^9,1{\leq}i{\leq}N)\) —— an array of integers.

It is guaranteed that the array is sorted in ascending order.


For each specific target, print only one line for the number of a numbers pairs \((a_i, a_j)\) satisfying \(a_i*a_j=M\).

Sample Input

-4 -4 -2 -1 0 1 2 2 4

Sample Output



Duplicate pairs \((a_i,a_j)\) count only once!