You have an array A and a number k. For any pair of numbers x,y from the array A let m be the minimum number such that lcm(x,y)*m is a multiple of k. Find the sum of all such m for all the pairs of A.
Constraint
- size of array(n)<=1e5
- each element of the array is between 1 and 1e9
Note Here you have to sum the m for all n^2 pairs

I used an prime factorization of the final number x as follows

Assume x exists and = p1^q1 * p2^q2... and so on where p1<p2<p3<....

For the largest divisor I divide x by p1 so b=x/p1;

Now for second largest (i.e. a) I have two choices I have to compare between p1^2(if q1=1 then we don't have this choice) and p2 If p1^2>p2 then the second largest should be a=x/p2; else a=x/(p1^2);

consider the first one x/p2=a; and x/p1=b; or, a*p2=b*p1; Eq-1

let m be the gcd of (a,b) then dividing both sides of Eq-1 by m(let a/m=a1 and b/m=b1) a1*p2=b1*p1; now a1 doesn't have any common factors with b1 so it completely divides p1 similarly, p1 doesn't have any common factor with p2 so it completely divides a1

Hence a1=p1 and b1=p2;

So if a1 and b1 are not primes this fails as we don't get them as the largest and second largest numbers.

now considering the second case.(Only applicable if q1>1) a=(x/p1^2) and b=(x/p1)
or, p1^2*a=b*p1 or, p1=(b/a);

Hence it is clear that if a divides b and b/a is prime then only it holds otherwise it fails

I am not quite sure whether there are some more conditions or Am i missing something?

I submitted my code, It ran cause the test cases were only those which have a and b as answers
239748609