Блог пользователя fsociety00

Maximize LCM
Автор fsociety00, история, 6 лет назад, По-английски

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

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    6 лет назад, # ^ |
    ← Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

    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.

    → Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить