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!