Popularitate

Prima varianta pentru rezolvarea acestei probleme este folosirea numerelor mari. Inmultim in prima faza toate numerele dintr-un grup si apoi le impartim la K atata timp cat restul impartirii este 0. Aceasta abordare obtine 30 de puncte.
Atunci cand K este prim, este de ajuns sa calculam puterea la care apare K in fiecare numar al grupului, fie acesta T_j. Atunci popularitatea grupului este P = T₁ + T₂ + ... + T_Ni. Aceasta abordare obtine 30 de puncte.
Un program care pentru K compus calculeaza P folosind prima metoda si pentru K prim calculeaza P folosind metoda a doua obtine 50 de puncte.
Solutia de 100 de puncte a problemei se bazeaza pe reducerea cazului in care K este compus la o varianta modificata a rezolvarii pentru K prim. Fie K = K₁^F₁ * K₂^F₂ * ... * K_Q^F_Q unde K₁, K₂ ... K_Q sunt factori primi distincti si presupunem ca F₁, F₂ ... F_Q > 0, In acest caz Q < log(K). Fie P_i popularitatea grupului calculata pentru K_i, atunci popularitatea grupului pentru K este min( [P_i / F_i] ) cu 1 ≤ i ≤ Q. Complexitatea finala este O(sqrt(K) + M*N*log(K)).