h3. (problema grea, clasa a 9-a, problema medie, clasa a 10-a)

Notam $A{~i~}$ multimea perechilor al caror produs se scrie sub forma {$x^i^$} cu {$x$} numar natural. Problema ne cere calcularea cardinalului reuniunii multimilor $A{~i~}$.
 
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 o matrice {$Nr[a][b][c]$} care reprezinta numarul de triplete (x,y,z) cu proprietatea {$a=x$},{$b=y$},{$c=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 o chestie 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:
 
==code(cpp) |
|S| = |A{~2~}| + |A{~3~}| + |A{~5~}| + ...
    - |A{~6~}| - |A{~10~}| - |A{~15~}| + ...
    + |A{~30~}| + ...
    - ...
==
 
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$}.
 
 

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