Problem statement,

you are given an array of positive integers of size n, and an integer k.
for each pair of (i, j) in the array, where 1 <= i <=n and 1 <= j <=n, m is the minimum value such that lcm(a[i], a[j]) * m is a multiple of k.
you need to find the sum of values of m. i.e find the m for each pair and then take the sum of these value.

constraints:
$$${1} \leq{n} \leq{10}^{5}$$$
$$${1} \leq{k} \leq{10}^{6}$$$
$$${1} \leq{a[i]} \leq{10}^{9}$$$

I encountered this problem in an OA.

if anybody can provide solution to this, I would be very happy.
Thanks In Advance!

I want to see how many reply will require on a single comment such that the last reply contains single character on each line.

According to wikipedia, Bitonic sort complexity is log^2n. Is it true ?