fsociety00's blog

Maximize LCM
By fsociety00, history, 6 years ago, In English

How we can break 'n' into parts such that LCM of parts is maximum (number of parts should be greater than or equal to 2)? OR Find A1, A2, ..., Ak such that A1 + A2 + ... + Ak = n and LCM(A1, A2, ..., Ak) is maximum. Here 2 <= k <= n. Original Problem Link: http://acm.timus.ru/problem.aspx?space=1&num=1807

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There is another important requirement in the original problem: first, GCD of all numbers should be the maximum possible. LCM should be maximized among such answers only.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 4   Vote: I like it +5 Vote: I do not like it

    Yeah. Maximum GCD is the maximum number which divides n. We can find that in O(sqrt(n)). So finally we have to maximize LCM for n/(maximum number which divides n) which is the smallest prime number which divides n. So that problem reduces to the problem which I mentioned in the blog.

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

Did you Solve this? it seems this is some DP problem, but i am unable to solve it too. It would be great if you share the solution if you solved it, or please someone share the solution approach to this problem.

→ Reply