Sum of LCM of all pairs in array in a way more efficient than o(n^2)

help
,
1
1 Like
2

Did anyone solve this ? If yes, kindly let me know about the approach. Thanks

1 Like
3

I also asked a similar question refer How to approach PRLCM on SPOJ?

1 Like
4

Let C_i denote the number of values j such that A_j = i.

i|j denotes i divides j.

Let us define

S_i = \sum_{gcd(A_j,A_k)=i} A_jA_k

Let us find the sum of pairs over all A_j,A_k such that both are divisible by i. This will give us all pairs such that gcd(A_j,A_k) is a multiple of i.

This is also equal to

\Bigg(\sum_{i|j}j\times C_j\Bigg)^2

So the sum of pairs such that gcd(A_j,A_k) = i is

S_i = \Bigg(\sum_{i|j}j\times C_j\Bigg)^2 - \sum_{i|j \& j\not=i} S_j

The final answer will be \sum \dfrac{S_i}{i}.

2 Likes