Se foloseste o singura data ciurul lui Erathostene pentru a determina functia phi pentru toate intrebarile. Se poate consulta "articolul":http://infoarena.ro/Ciurul_lui_Erathostene despre cirulul lui Erathostene.

O alta solutie, propusa de Bogdan A. Stoica, se bazeaza pe principul includerii si excluderii. Din enuntul problemei ne dam seama ca suma ceruta este suma tuturor numerelor $z$ cu proprietatea ca {$cmmdc(z, x) = 1$}. Pentru a afla aceste numere este de ajuns sa observam ca $cmmdc(z, x) != 1$ daca si numai daca exista cel putin un $p{~i~} = q{~j~}$ unde {$z = p{~1~}^e{~1~}^&#0042; ... &#0042;p{~n~}^e{~n~}^$}, iar {$x = q{~1~}^f{~1~}^&#0042; ... &#0042;q{~m~}^f{~m~}^$}. Fie doua astfel de numere {$p{~i~} = q{~j~}$}. Noi trebuie sa afla suma tuturor numerelor care se divid cu $p{~i~}$ si sunt in intervalul [{$0, 2*x$}]. Aceste numere sunt : {$p{~i~}, 2&#0042;p{~i~}, ..., k&#0042;p{~i~}$}, $0 < k &le; {$[2&#0042;x/p{~i~}]$}. Suma acestor numere se poate scrie ca {$p{~i~} + ... + k&#0042;p{~i~}$}, adica pi(1+...+k) adica {$p{~i~}&#0042;k(k+1)/2$}. De aici suntem tentati sa credem ca suma ceruta (fie aceasta {$S$}) este $S$ = {$x(2&#0042;x-1) - p{~1~}&#0042;k{~1~}&#0042;(k{~1~}+1)/2 - .... - p{~n~}&#0042;k{~n~}&#0042;(k{~n~}+1)/2$}. La o citire mai atenta observam ca am scazut unele de doua ori (cele care se divid si cu $p{~1~}$ si cu {$p{~2~}$}, de exemplu) si nu am scazut deloc alte numere care au un divizor comun cu $x$ mai mare decat $1$ (cele care se divid simultan cu {$p{~1~}$}, $p{~2~}$ si {$p{~3~}$}, de exemplu). Astfel, aplicand principiul includerii si excluderii putem schita formula finala : {$S = x&#0042;(2x-1) - p{~1~}&#0042;k{~1~}&#0042;(k{~1~}+1)/2 - ... + p{~1~}&#0042;p{~2~}&#0042;k'{~1~}(k'{~1~}+1)/2 + ... - p{~1~}&#0042;p{~2~}&#0042;p{~3~}&#0042;k''{~1~}(k''{~1~}+1)/2 + ...$}, adica vom scadea toti termenii care se obtin prin inmultirea a unui numar impar de factori primi si vom aduna restul. Aceasta solutie obtine in jur de $80$ de puncte pe restul testelor depasind timpul de executie.

O alta solutie, propusa de Bogdan A. Stoica, se bazeaza pe principul includerii si excluderii. Din enuntul problemei ne dam seama ca suma ceruta este suma tuturor numerelor $z$ cu proprietatea ca {$cmmdc(z, x) = 1$}. Pentru a afla aceste numere este de ajuns sa observam ca $cmmdc(z, x) != 1$ daca si numai daca exista cel putin un $p{~i~} = q{~j~}$ unde {$z = p{~1~}^e{~1~}^&#0042; ... &#0042;p{~n~}^e{~n~}^$}, iar {$x = q{~1~}^f{~1~}^&#0042; ... &#0042;q{~m~}^f{~m~}^$}. Fie doua astfel de numere {$p{~i~} = q{~j~}$}. Noi trebuie sa afla suma tuturor numerelor care se divid cu $p{~i~}$ si sunt in intervalul [{$0, 2*x$}]. Aceste numere sunt : {$p{~i~}, 2&#0042;p{~i~}, ..., k&#0042;p{~i~}$}, {$0 < k &le; [2&#0042;x/p{~i~}]$}. Suma acestor numere se poate scrie ca {$p{~i~} + ... + k&#0042;p{~i~}$}, adica pi(1+...+k) adica {$p{~i~}&#0042;k(k+1)/2$}. De aici suntem tentati sa credem ca suma ceruta (fie aceasta {$S$}) este $S$ = {$x(2&#0042;x-1) - p{~1~}&#0042;k{~1~}&#0042;(k{~1~}+1)/2 - .... - p{~n~}&#0042;k{~n~}&#0042;(k{~n~}+1)/2$}. La o citire mai atenta observam ca am scazut unele de doua ori (cele care se divid si cu $p{~1~}$ si cu {$p{~2~}$}, de exemplu) si nu am scazut deloc alte numere care au un divizor comun cu $x$ mai mare decat $1$ (cele care se divid simultan cu {$p{~1~}$}, $p{~2~}$ si {$p{~3~}$}, de exemplu). Astfel, aplicand principiul includerii si excluderii putem schita formula finala : {$S = x&#0042;(2x-1) - p{~1~}&#0042;k{~1~}&#0042;(k{~1~}+1)/2 - ... + p{~1~}&#0042;p{~2~}&#0042;k'{~1~}(k'{~1~}+1)/2 + ... - p{~1~}&#0042;p{~2~}&#0042;p{~3~}&#0042;k''{~1~}(k''{~1~}+1)/2 + ...$}, adica vom scadea toti termenii care se obtin prin inmultirea a unui numar impar de factori primi si vom aduna restul. Aceasta solutie obtine in jur de $80$ de puncte pe restul testelor depasind timpul de executie.

h2. Pavare 2

{$|f{~E{~1~}~}| + |f{~E{~2~}~}| + ... + |f{~E{~N~}~}|$}
{$- |f{~E{~1~}~} ∩ f{~E{~2~}~}| - |f{~E{~1~}~} ∩ f{~E{~3~}~}| - ...$} (toate perechile)

{$+ |f{~E{~1~}~} ∩ f{~E{~2~}~} ∩ f{~E{~3~}~}| ... $}(toate tripletele)

{$+|f{~E{~1~}~} ∩ f{~E{~2~}~} ∩ f{~E{~3~}~}| ...$}(toate tripletele)

{$...$}

{$+ (-1)^n-1^ |f{~E{~1~}~} ∩ f{~E{~2~}~} ∩ ... ∩ f{~E{~N~}~}|$}

{$+(-1)^n-1^ |f{~E{~1~}~} ∩ f{~E{~2~}~} ∩ ... ∩ f{~E{~N~}~}|$}

Ce reprezinta intersectia ("∩") in acest context?
Daca $A = (a{~1~}, a{~2~}, ..., a{~K~})$ si {$B = (b{~1~}, b{~2~}, ..., b{~K~})$}, $A ∩ B$ va fi multimea ce contine toate experimentele despre care se stie cu siguranta ca vor esua, atat conform lui $A$ cat si lui {$B$}. Altfel spus, $A ∩ B$ = multimea experimentelor care vor esua conform {$(max(a{~1~}, b{~1~}), max(a{~2~}, b{~2~}), ..., max(a{~K~}, b{~K~}))$}.