[xp]

In cazul in care exista x_p numere care se divid cu p atunci exista Combin(x_p,2) perechi de numere neprime intre ele. Problema este ca pot exista perechi de numere care au mai multi divizori comuni. Si atunci acestea vor fi numarate de mai multe ori.

Sa consideram urmatoarele numere: 15, 105, 165. Pentru p=3 vor exista 3 perechi de numere pe care le vom aduna la Res. Pentru p=5, la fel. Cand ajungem la p=15 vom scadea 3 perechi obtinand astfel rezultatul corect. 15 este produs de 2 numere prime si asta inseamna ca perechile neprime care se formeaza pentru p=15 au fost numarate o data pentru p=3 si inca o data pentru p=5. Si atunci trebuie sa le scadem.

Cand p este produs pe 3 numere prime p=a*b*c, perechile trebuie adunate iar, pentru ca au fost scazute de prea multe ori. Astfel: au fost adunate pentru p=a, p=b, p=c si scazute pentru p=a*b, p=b*c, p=a*c. Asa ca trebuie adunate iar.

Numerele p a caror descompunere in factori primi contine acelasi termen de mai multe ori nu prezinta interes pentru ca perechile de numere neprime intre ele care corespund acestor numere p au fost numarate anterior pentru acele valori p=p', unde p' contine termenii lui p luati o singura data.

Sper ca explicatia mea este corecta si suficient de clara.

M-am prins cand m-am uitat mai atent. Mersi.

Am citit solutia problemei si din A_i,j = Suma(A_i+1,k * A_k+1,j | i < k < j si C_i+1 = C_k) inteleg ca arborele este binar. Din textul problemei nu reiese asta (sau cel putin nu m-am prins eu).

Mie mi-a placut concursul. Sper sa mai fie inca unul pana incepe scoala.

merci mult. n-am stiut ca e de la preONI.

stiu sa inmultesc matrici, dar nu-mi dau seama cum sa folosesc treaba asta in problema

Care e smecheria cu inmultirea de matrice? Ca nu ma prind deloc.

Am primit newsletter referitor la mutarea serverului de 2 ori, dar nici unul dintre mesaje nu era pe numele meu.