[concurs] Facebook Hacker Cup Round 2

[•CezarMocan]

Sambata, 5 Februarie 2011, de la ora 23:00, va avea loc Facebook Hacker Cup Round 2 .

[•vladii]

Salut! Acum ca s-a terminat runda, vreau sa va intreb si eu ceva la problema Bonus.
Am avut si eu o idee, am luat 0 pe ea, dar sunt curios daca este corecta (deci am gresit la implementare) sau este gresita ca idee.

Am o functie solve(int st, int dr) care imi spune cite siruri de N elemente au gcd = 1. Stiind asta, rezultatul se obtine in genul: solve(A, D) + solve(B+1, C-1) - solve(A, C-1) - solve(B+1, D).
Acum... ce fac in solve() ? Imi tin 2 vectori
P[ i ] = numarul de elemente divizible cu i din intervalul [st, dr];
put[ i ] = i ^ N;
Numarul total de siruri este put[ dr - st + 1 ], deci daca as afla "nr" = numarul total de siruri cu N elemente cu gcd > 1, atunci solve() returneaza put[ dr - st + 1] - nr.
Ca sa aflu "nr" am facut ceva gen principiul includerii si excluderii:
nr = put[ P[2] ] + put[ P[3] ] - put[ P[2*3] ] + put[ P[5] ] - put[ P[2*5] ] - put[ P[3*5] ] + put[ P[7] ] - put[ P[2*7] ] - put[ P[3*7] ] - put[ P[5*7] ] + ...
Cu alte cuvinte, adun put[ P[ x ] ] daca x este prim si scad put[ P[ x ] ] daca x este produs de fix 2 numere prime. (evident x = 2 -> dr).

LE: Mi-am dat seama ca este gresita ultima parte, am constientizat dupa ce am stins calculatorul ), trebuia facut EXACT ca la principiul includerii si excluderii, adica adaugam put[ P[ x ] ] daca x se scria FIX ca un produs de un numar impar de numere prime diferite si il scadeam daca x se scria FIX ca un produs de un numar par de numere prime diferite (fara ca acelasi numar prim sa apara de doua ori in descompunerea lui x)...

Cam asta este tot. As fi recunoscator daca v-ati uita 2 minute peste ceea ce am scris sau daca mi-ati impartasi ideea voastra de rezolvare. Multumesc mult! Vlad.