In continuare vom arata un mod de a calcula cardinalul unei multimi multimi {$A{~i~}$}. Se observa ca o pereche (a,b,c) (x,y,z) apartine multimii {$A{~i~}$} daca {$a+x=0$},{$b+y=0$} si {$c+z=0$} (mod {$i$}). Vom constui un tablou {$Nr[r1][r2][r3]$} care reprezinta numarul de triplete (x,y,z) cu proprietatea {$r1=x$},{$r2=y$},{$r3=z$} (mod {$i$}). Vom adauga la cardinalul multimii {$A{~i~}$} produse de forma {$Nr[a][b][{@c@}]*Nr[i-a][i-b][i-c]$} ({$i-a,i-b,i-c$} se calculeaza tot mod {$i$}). Deasemenea trebuie avut grija la numerele pentru care {$2*a=0$} {$2*b=0$} si {$2*c=0$} (mod {$i$}), deoarece trebuie adunat $Nr[a][b][{@c@}]*(Nr[a][b][{@c@}]-1)/2$ pentru a nu numara aceeasi pereche de mai multe ori.

O observatie care ne va ajuta sa calculam cardinalul reununiunii este faptul ca daca un numar se scrie de forma $x^i*j^$ el se scrie si de forma $y^i^$ unde $y$ va fi chiar $x^j^$. Asadar $A{~i*j~}$ este inclusa in {$A{~i~}$}. Deci ne va interesa reuniunea multimilor {$A{~i~}$} pentru $i$ numar prim. Cardinalul acestei reuniunii se va calcula folosind principiul includerii si excluderii:

O observatie care ne va ajuta sa calculam cardinalul reununiunii este faptul ca daca un numar se scrie de forma $x^i*j^$ el se poate scrie si sub forma {$y^i^$}, unde $y$ va fi chiar $x^j^$. Asadar $A{~i*j~}$ este inclusa in {$A{~i~}$}. Deci ne va interesa reuniunea multimilor {$A{~i~}$} pentru $i$ produs de numere prime. Cardinalul acestei reuniunii se va calcula folosind principiul includerii si excluderii:

==code(cpp) |
|S| = |A[2]| + |A[3]| + |A[5]| + ...

    - ...
==

Cardinalul multimii $A{~i~}$ se adauga la solutie in cazul in care are un numar impar de divizori primi si se va scadea din solutie daca are un numar par de divizori. Termenii pentru care in descompunerea lui $i$ apare un factor la putere mai mare de $1$ vor fi ignorati. Datorita limitarilor din enunt nu va trebui sa verificam decat multimile $A{~i~}$ cu {$i ≤ 128$}.

Cardinalul multimii $A{~i~}$ se adauga la solutie in cazul in care $i$ are un numar impar de divizori primi si se va scadea din solutie daca are un numar par de divizori. Termenii pentru care in descompunerea lui $i$ apare un factor la putere mai mare de $1$ vor fi ignorati. Datorita limitarilor din enunt nu va trebui sa verificam decat multimile $A{~i~}$ cu {$i ≤ 128$}.

h2. 'Balanta':problema/balanta
h3. (problema usoara, clasa a 10-a)

Problema se rezolva mentinand doua multimi $H$ si $L$ continand monedele candidate pentru moneda mai grea, respectiv cele candidate pentru moneda mai usoara. Initial $H$ si $L$ contin fiecare toate elementele multimii @{1..N}@. Cele doua multimi se vor actualiza dupa fiecare cantarire. Notand cu $A$ multimea monedelor asezate pe bratul stang si cu $B$ multimea monedelor asezate pe bratul drept al balantei, vom proceda in felul urmator:
 
* talerele sunt echilibrate - este clar ca nici una din monedele din $A$ sau $B$ nu poate fi mai grea/mai usoara, deci $H$ va deveni $H - A - B$, iar $L$ va deveni $L - A - B$
 
* talerul stang este mai greu - moneda falsa, in caz ca este mai grea, se va afla cu siguranta in multimea $A$ sau, in caz ca este mai usoara, se va afla in multimea $B$. Astfel, $H$ devine $H ∩ A$, iar $L$ devine $L ∩ B$
 
* talerul drept este mai greu - caz simetric cu cel anterior, $H$ devine $H ∩ B$, iar $L$ devine $L ∩ A$.
 
La final vom avea solutie daca si numai daca $|H| = 1 si |L| = 0$, caz in care moneda falsa este mai grea, sau $|H| = 0 si |L| = 1$, cand moneda falsa este mai usoara.
 
Complexitatea algoritmului care rezolva problema este $O(M*N)$.
 

h2. 'Expresii 2':problema/expresii2
h3. (problema grea, clasa a 10-a)