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.

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: