MehrajShakil's blog

By MehrajShakil, history, 7 days ago, In English,

In this problem, I have to find sum of all pairs lcm of an array. I find this from morass blog.Can anyone explain it. Thanks in advance.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

https://proofwiki.org/wiki/GCD_and_LCM_Distribute_Over_Each_Other

Using this property, you can solve it with prefix gcd. I think this is an efficient way. it can be solved in o(n) now. You can study the blogs written about the problem "Orac and LCM". This may help you