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