(Creat de ==user(user="silviug" type="tiny")== la data de _2005-02-25_ categoria _Competitii_, autor(i) _Echipa devNet_)

==Include(page="template/raw")==
 

Desi s-a desfasurat intr-o zi de miercuri, runda a doua a concursului preONI a avut un numar aproape dublu de accesari fata de runda 1. Acest lucru se datoreaza probabil atat faptului ca olimpiada judeteana "bate la usa" cat si prezentei premiilor oferite de sponsorul nostru, Microsoft Romania.
In continuarea acestui articol vom descrie solutiile oficiale ale problemelor. Daca aveti nelamuriri puteti sa puneti intrebari pe "forum":http://www.infoarena.ro/Forum.

Cea de-a doua solutie, cu mult mai interesanta decat prima, foloseste principiul includerii se excluderii. Fie $D(x)$ multimea numerelor din sir care sunt divizibile cu un anumit numar {$x$}, atunci numarul de submultimi formate doar din astfel de numere este {$Z(x) = 2^card(D(x))^-1$}. Multimile pentru principiul includerii si excluderii sunt chiar {$D(p)$}, unde $p$ este un numar prim. Intersectia {$D(p{~1~})$}, {$D(p{~2~})$}, {$D(p{~3~})$}.. este {$D(p{~1~} * p{~2~} * p{~3~}...)$}, oarecum evident, pentru $p$ distincte. Rezultatul este de forma:

$Rezultat = Z(1) - Z(2) - Z(3) - Z(5)... +$
$Z(2 * 3) + Z(2 * 5) + Z(3 * 5)... -$
$Z(2 * 3 * 5) ...$

== code(cpp) |Rezultat = Z(1) - Z(2) - Z(3) - Z(5)... +
           Z(2 * 3) + Z(2 * 5) + Z(3 * 5)... -
           Z(2 * 3 * 5) ...
==

Acesta se deduce din principiul includerii si al excluderii. Pentru a-l calcula efectiv, luam toate numerele {$x < 1000$}, produs de numere prime distincte, si vom adauga sau scadea $Z(x)$ in functie de paritatea numarului de factori ai acestuia. Nu ne intereseaza decat produsele de numere prime distincte, care pot fi obtinute ca un produs {$p{~1~}*p{~2~}*p{~3~}$}... Complexitatea finala este sub {$O(N*K + N*L)$}, unde $K$ si $L$ au semnificatia de mai sus. Folosim $O(N*K)$ pentru a calcula $D(x)$ pentru fiecare {$x$}, dar pentru fiecare $x$ adunam sau scadem $Z(x)$ o singura data, asa ca facem doar $N$ operatii pe numere mari, o imbunatatire majora asupra primei rezolvari. Pentru a obtine aceasta complexitate este nevoie sa precalculam valorile lui $2^x^$ in {$O(N * L)$}, altfel ca sa calculam $Z(x)$ pentru fiecare ar fi nevoie de $O(L * X)$ timp.