Question
Count Power Pairs
In a factory, you have a list of N machines, each with a specific power level Pi. You’re given a threshold value K and need to find how many pairs of machines (i, j) (where 1 ≤ i < j ≤ N) have a combined power (the product of their power levels) greater than or equal to K. Your task is to calculate and report the total number of such powerful machine pairs.
Input
First line of the input contains two integers N and K.
The second line of the input contains N space-separated integers.
Constraints
1 ≤ N ≤ 105
1 ≤ K ≤ 1012
1 ≤ Ai ≤ 106
The second line of the input contains N space-separated integers.
Constraints
1 ≤ N ≤ 105
1 ≤ K ≤ 1012
1 ≤ Ai ≤ 106
Output
Print the number of pairs of indices i, j (1 ≤ i < j ≤ N) such that Ai x Aj >= K.
Example
Sample Input
7 20
5 7 2 3 2 9 1
Sample Output
5
Explanation
The following pairs of indices satisfy the condition (1-based indexing)
(1, 2) -> 5 * 7 = 35
(1, 6) -> 5 * 9 = 45
(2, 4) -> 7 * 3 = 21
(2, 6) -> 7 * 9 = 63
(4, 6) -> 3 * 9 = 27
All these products are greater than or equal to K (= 20).
Sample Input
3 4
2 2 2
Sample Output
3
Explanation
The following pairs of indices satisfy the condition (1-based indexing)
(1, 2) -> 2 * 2 = 4
(1, 3) -> 2 * 2 = 4
(2, 3) -> 2 * 2 = 4
All these products are greater than or equal to K (= 20).
7 20
5 7 2 3 2 9 1
Sample Output
5
Explanation
The following pairs of indices satisfy the condition (1-based indexing)
(1, 2) -> 5 * 7 = 35
(1, 6) -> 5 * 9 = 45
(2, 4) -> 7 * 3 = 21
(2, 6) -> 7 * 9 = 63
(4, 6) -> 3 * 9 = 27
All these products are greater than or equal to K (= 20).
Sample Input
3 4
2 2 2
Sample Output
3
Explanation
The following pairs of indices satisfy the condition (1-based indexing)
(1, 2) -> 2 * 2 = 4
(1, 3) -> 2 * 2 = 4
(2, 3) -> 2 * 2 = 4
All these products are greater than or equal to K (= 20).