Pentru n prim, putem face doua observatii:
1) Cmmdc-ul numerelor ce dau suma n va fi 1.
Dem.: Fie v1, v2..vk, astfel incat v1+v2+..+vk = n
Cmmdc(v1, v2..vk) divide n, dar n este prim, rezulta cmmdc = 1. (daca cmmdc = n rezulta k = 1 contradictie).
Acum, considerand cazul n compus, putem face urmatoarea observatie:
v1 = cmmdc * x1, v2 = cmmdc * x2 .. vk = cmmdc * xk
Noi vrem sa calculam cmmmc (v1, v2, .. vk).
Cmmmc(v1, v2 .. vk) = cmmdc(v1, v2..vk) * cmmmc(x1, x2 .. xk).
Stim ca suma x1 + x2 + ... + xk = S <= sqrt(n). (Alegem cmmdc-ul maxim => n / cmmdc <= sqrt(n)).
Problema se reduce la a gasi termenii x1, x2, .. xk astfel incat cmmmc(x1, x2, .. xk) sa fie maxim.
Acest lucru se poate rezolva cu o dinamica S * nr_prim, unde nr_prim reprezinta numarul de numere prime <= S.
2) Daca n ar fi prim, atunci x1 + x2 + .. + xk = v1 + v2 + .. + vk = n, deci solutia ar rula in O(n * nr_factori_primi <= n), ce ar depasi limita de timp, si ar forta o restrictie destul de stransa pentru n, gen 3000.
De aici vine restrictia n compus. Nu stiu daca exista un algoritm pur greedy pentru a genera cmmmc-ul maxim, si din ce stiu, toti cei care au luat 100 in concurs s-au bazat pe abordarea folosind programare dinamica.
Sper sa nu ma insel
.