Muhammad_mhs's blog

Please Help [LCM related Problem]
By Muhammad_mhs, history, 5 years 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

Comments Comments (2)
| Write comment?
»
5 years 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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You need to read the problem again I guess!!

    → Reply