Analiza

U ovom zadatku traži se da se nađe broj uređenih parova $(i, j), 1 \leq i < j \leq N$ tako da su $A_i, A_j$ uzajamno prosti brojevi. Za svaka dva broja $x, y$ možemo direktnom proverom, u vremenskoj složenosti $O(min(x, y))$ proveriti da li postoji neki prirodan broj, veći od $1$, koji deli oba ova broja. Ovakav algoritam je dovoljan za rešavanje prvog podzadatka. Za drugi podzadatak možemo koristiti Euklidov algoritam, koji u samo $O(log(min(x, y)))$ deljenja nalazi NZD dva broja. Međutim, ovaj algoritam nije dovoljan za treći podzadatak -- operacije deljenja su veoma skupe. Zato, za treći, a i četvrti podzadatak, prvo potražimo sve proste brojeve do $\sqrt{10^8} = 10^4$, npr. pomoću Eratostenovog sita, a zatim pomoću ovih brojeva faktorišimo sve date brojeve, odnosno, napišimo ih u obliku proizvoda prostih brojeva. Primetimo da su dva broja uzajamno prosta ako i samo ako njihove liste prostih delilaca nemaju nijedan zajednički element, što znači da pri pamćenju listi prostih delilaca možemo izostaviti duplikate. Pošto je $2 \times 3 \times \5 times \7 \times 9 \times 11 \times 13 \times 17 \times 19 > 10^8$, nijedan od datih brojeva neće imati više od $8$ različitih prostih delilaca. Za treći podzadatak, za svaka dva broja uporedimo njihove liste prostih delilaca i na ovaj način ispitujemo da li su oni uzajamno prosti. Ovaj korak se može uraditi u vremenskoj složenosti $O(k+l)$, gde su $k, l$ dužine listi za te brojeve, ako prethodno sortiramo sve ove liste. Za maksimalan broj poena možemo koristiti sledeći postupak. Prvo, modifikujmo postavku problema. Umesto broja uređenih parova oblika $(i, j), 1 \leq i < j \leq N$ potražimo broj uređenih parova oblika $(i, j), 1 \leq i, j \leq N$. Od broja ovakvih parova treba oduzeti broj parova oblika $(i, i), 1 \leq i \leq N$, odnosno, broj jedinica u datom nizu, a zatim podeliti ovu razliku sa $2$. Zatim, za svaki broj iz datog niza izračunajmo sve "bezkvadratne" delioce -- one koji nisu deljivi kvadratom nijednog prostog broja. Ako broj $x$ ima $q$ različitih prostih delioca, onda on ima tačno $2^q$ bezkvadratnih delioca. Ovo možemo efikasno uraditi pomoću već dobijene proste faktorizacije. Naš cilj je da možemo za svaki bezkvadratni broj da efikasno proverimo koliko brojeva iz datog niza je deljivo tim brojem. Ovo možemo uraditi na više načina, brojanjem i/ili sortiranjem svih nađenih bezkvadratnih delioca. Zatim, za neki broj $x$ čiju prostu faktorizaciju imamo, možemo proveriti koliko brojeva iz datog niza je uzajamno prosto sa njim pomoću principa uključenja-isključenja i prethodno pomenute provere. Prvo, uzmimo da su svi brojevi iz datog niza uzajamno prosti sa $x$. Zatim, izbacimo sve one koji su deljivi sa $p_1, p_2, ..., p_q$ pa ubacimo one koji su deljivi sa $p_1 p_2 , p_1 p_3, ..., p_{q-1} p_q$, itd. Izraz za konačnu vremensku složenost ovog algoritma je dosta komplikovan i stoga izostavljen. Ovo je dovoljno brzo i za poslednji, najopštiji podzadatak.

Napomene

Brojanje bezkvadratnih delioca može se postići na više načina, kombinacijom sortiranja i binarne pretrage, brojanjem (slično Counting Sort-u) za dovoljno male vrednosti, ili smeštanjem u mapu (C++).