h2(#pairs). 'Pairs':problema/pairs

Problema admite o rezolvare triviala de complexitate {$O(N^2^log MAX)$}, unde $MAX$ este maximul dintre cele $N$ numere ale multimii {$M$}: pentru fiecare pereche de numere din multimea data se calculeaza cel mai mare divizor comun folosind algoritmul lui Euclid. O astfel de rezolvare obtine 20-30 de puncte, in functie de prezenta unor optimizari. Rezolvarea optima are complexitatea {$O(MAX log MAX)$} si se baza pe faptul ca {$O(N/1 + N/2 + N/3 ... + N/N)$} = {$O(N log N)}$, pentru orice {$N$}.
Fie {$x{~i~}$} numarul de numere din $M$ care se divid cu {$i$}. Vectorul $x$ se poate calcula in {$O(MAX log MAX)$}: pentru fiecare numar $i$ de la $1$ la $MAX$ verificam cate din numerele {$i$}, {$2i$}, {$3i$} ... apartin multimii {$M$}. Din numarul total de perechi, {$N * (N-1) / 2$}, vom scadea numarul de perechi {$(x y)$}, astfel incat x si y nu sunt prime intre ele si vom obtine rezultatul cerut.
Pentru a afla care perechi {$(x y)$}, cu {$cmmdc(x, y) > 1$}, exista, vom folosi procedeul matematic numit includere si excludere. Fie {$Res$} numarul acestor perechi. Consideram toate numerele P ce se scriu ca produs de numere prime, unde fiecare numar prim este folosit cel mult o data. Daca numarul de numere impare din descompunerea lui P este un numar impar, adunam {$x{~P~}$} la {$Res$}. Altfel, din {$Res$} scadem {$x{~P~}$}.
 
 

h2(#aliens). 'Aliens':problema/aliens
h2(#tunel). 'Tunelul groazei':problema/tunel