A Problem

Revision en2, by brown-Rang, 2024-09-10 11:22:23

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.

$$${s} = \sum_{i=1}^{n}\sum_{j=1}^n {m}$$$

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!

Tags problem, number theory, online assessment

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English brown-Rang 2024-09-10 11:22:23 33 Tiny change: '/>\n$$\sum$$\nconstr' -> '/>\n$$\sum_{i=1}^{n}\sum_{j=1}^n {m}$$\nconstr' (published)
en1 English brown-Rang 2024-09-10 11:19:39 654 Initial revision (saved to drafts)