Revizia anterioară Revizia următoare
Solutii preONI 2008, Runda 1
comentarii aici...
Ordine
Multimi 2
Ecuatie
Economie
Teren
Pairs
Problema admite o rezolvare triviala de complexitate O(N2log 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 xi 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 prime din descompunerea lui P este un numar impar, adunam xP la Res. Altfel, din Res scadem xP.
