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 pi = qj unde z = p1^e1*...*pn^2n, iar x = q1^f1*....*qm^fm. Fie doua astfel de numere pi = qj. Noi trebuie sa afla suma tuturor numerelor care se divid cu pi si sunt in intervalul [0, 2*x]. Aceste numere sunt : pi, 2*pi, ..., k*pi, 0 < k <= [2*x/pi]. Suma acestor numere se poate scrie ca pi +....+ k*pi, adica pi(1+...+k) adica pi*k(k+1)/2. De aici suntem tentati sa credem ca suma ceruta (fie aceasta S) este S = x(2*x-1) - p1*k1*(k1+1)/2 - .... - pn*kn*(kn+1)/2. La o citire mai atenta observam ca am scazut unele
de doua ori (cele care se divid si cu p1 si cu p2, 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 p1, p2 si p3, de exemplu). Astfel, aplicand principiul includerii si excluderii putem schita formula finala : S = x*(2x-1) - p1*k1*(k1+1)/2 - ... + p1*p2*k'1(k'1+1)/2 + ... - p1*p2*p3*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

 
Pavare 2
 
(problema grea, clasa a 10a)

h3. (problema grea, clasa a 10a)

Problema se rezolva cu programare dinamica. Utilizam urmatoare structura de date:

* V[i][j][0] *C numarul de posibilitati pentru a pava i metri astfel incat primele j placi sa fie albe

* $V[i][j][0] *C$ numarul de posibilitati pentru a pava i metri astfel incat primele j placi sa fie albe

* V[i][j][1] *C numarul de posibilitati pentru a pava i metri astfel incat primele j placi sa fie negre
Relatiile de recurenta sunt acum usor de dedus. Odata calculata matricea putem raspunde foarte usor primei cerinte, facand suma V[N][i][0] (pentru 1 <= i <= A) si V[N][i][1] pentru (1 <= i <= B).