Analiza

Prvo, za svaki broj sa ulaza nađimo sve različite proste brojeve koji ga dele. Ovo se može uraditi efikasno pomoću modifikacije Eratostenovog sita, kojom se svaki broj x < M može faktorizovati u logaritamskoj složenosti, gde je M gornja granica za Eratostenovo sito.

Ovih različitih prostih brojeva ima ne više od 6, jer je proizvod najmanjih 7 prostih brojeva veći od 2 \times 10^5. Sada, za svaki broj nađimo količnik njega i svakog različitog prostog broja koji ga deli. Neka je za i-ti broj P_i lista njegovih različitih prostih delilaca a C_i lista koja se dobija kada se A_i podeli sa svakim elementom liste P_i. Cilj zadatka je da nađemo niz različitih brojeva B tako da je za svako i, B_i = A_i / P_{i, j} = C_{i, j} za neko j. Ovaj problem je poznat i pod nazivom sistem različitih predstavnika familije skupova C. Ovo se može rešiti u polinomijalnom vremenu tako što se predstavi kao bipartitni graf, gde su čvorovi sa leve strane indeksi iz originalnog niza, a sa desne strane količnici. Za svako i dodajemo granu od čvora i sa leve strane do čvorova C_{i, j} sa desne, za svako j. Svaki sistem različitih predstavnika sada odgovara jednom perfektnom sparivanju (mečingu) u ovom grafu, odnosno mečingu gde je svaki čvor sa leve strane sparen. Dakle želimo da ispitamo da li ovako dobijen graf ima mečing sa N grana i koji je to mečing.

Najjednostavniji i najpoznatiji algoritam jeste Ford-Fulkersonov algoritam koji radi u složenosti O(VE), gde je V broj čvorova, a E broj grana u grafu, što u našem slučaju, zbog gore pomenutog ograničenja na broj grana iznosi O(N^2). Primetimo da ne moramo da dodajemo sve čvorove sa desne strane već samo one koji se bar jednom pojavljuju kao količnici.