infoarena

Aici puteţi discuta despre problema Puternic (http://infoarena.ro/problema/puternic).

 :-' Cam cat de mare este al 180-lea numar puternic ? ....am generat toate cele mai mici numere care au exact k-divizori unde k = 1..80.000 si am gasit doar primele 156 de numere puternice.  #-o

Eu pentru 100 de puncte am generat 300 000. Am ales 180 a. i. ultimele doua teste sa depaseasca si long long.

Exista divizor prim al celui de-al 180-lea numar puternic mai mare decat al 100-lea numar prim?

De fapt, eu am folosit doar primele 18 numere prime, si nici astea nu intrau toate... Din cate am vazut, factorii primi care trebuiau luati erau cam pana la 47 ( deci 15 la numar ). Daca puneam un numar de numere prime mult mai mare, rezultatul ramanea acelasi.

Si totusi...cum afli cel mai mic numar cu exact K divizori? :?...

Faci o dinamica A[ i, j ] = cel mai mic numar cu exact J divizori obtinut folosind primele i numere prime
Recurentza o scoti tu, ca nu e greu  8)

recurenta merge...e usor, dar, unde se afla rezultatul?...scuze ca intreb, dar nu ma prea descurc...

 Pentru un J fixat ( adica exact J divizori ) rezultatul se gaseste in A[ i, j ] / unde i are valoarea maxima. De exemplu daca folosesti in dinamica primele 18 numere prime, rezultatul va fi A[ 18, j ].  :thumbup:

O fi simpla recurenta, dar eu nu ma prind :(
Puteti sa mai imi dati un mic hint...cum ar fi complexitatea dinamicii?

Anyway...don't spoil the fun...

Pai numarul este de forma p1^k1 * p2^k2 * p3^k3 .......unde Pi = numarul prim si Ki = puterea la care apare factorul prim Pi...si acuma se cam vede cum se trece dintr-o stare in alta... ( cand  inmultesti cu un numar prim mai mare decat toate din descompunere..vezi cam cu cat creste numarul diviziorilor... )
 

Bun...dar daca A[i,j] (respectand notatia de mai sus) vreau sa-l inmultesc cu un pk (k<=i, pk-> al k-lea numar prim) atunci am nevoie de puterea la care se afla acesta in descompunerea lui A[i,j]...Si de aici vad doua posibilitati:
1. sa descompun fiecare A[i,j]...ceea ce nu mi se pare convenabil si ar avea o complexitate mare sau
2. sa pastrez exponentii fiecarui numar prim, dar nu imi ajunge memoria

Ce n-am inteles bine sau cum as putea imbunatati?

mam gadit si eu la rezolvarea cu sa calculez cele mai mici numere cu k divizori dar mia fost mult prea lene sa stau sa vad cate trebuie sa generez (zicand ca sunt prea multe) asa ca am facut urmatoarea chestie (pe care bineinteles nu stiu so demonstrez sau daca chiar e valabila  :D )

un numar puternic se obtine din alt numar puternic mai mic inmultit cu unul din primele cateva numere prime (asta e logic dar nush daca chiar il prind pe cel mai mic dintre ele  :D) (din toate posibilitatile am luat-o pe cea mai mica)....
si pe aceasta observatie am reusit sa iau 100 cu un timp relativ mic fara precalculare (0.25 secunde)

cam care sunt primele 10 numere puternice?

1
2
4
6
12
24
36
48
60
120

Eu am facut cu un ciur si am retint in v[ i ] cati divizori are i si dupaia miam construit vectorul cu numere puternice si am afisat C[N] rezolvarea asta nu e deloc eficienta ptr ca am luat doar 20 de p . Daca vreti spuneti-mi si mie o alta metoda de rez care mar duce la un punctaj maxim

A postat Vlad Berteanu mai sus rezolvarea problemei.

Eram sigur ca asta raspundeti.

Si atunci de ce ai mai postat?

Ma gandeam ca exista alta solutie mai Eleganta ... si ma mai gandeam ca ma puteti ajuta dar se pare ca m-am inselat....

De obicei inainte sa postezi ar fi bine sa citesti topicul, oricum, din ce ai scris s-a inteles ca nu sti o solutie de 100, nu ca ai vrea sa sti alta solutie in afara de cea prezentata mai sus...

Problema asta nu e tocmai usoara pentru un incepator. Doar pentru ca rezolvarea nu iti iese in 5 linii de cod nu inseamna ca nu este "eleganta".

Incearca sa rezolvi probleme mai usurele de dinamica si dupaia reintoarce-te al aceasta :).

Te inseli daca crezi ca nu vreu sa stiu o solutie de 100 de p daca nu vreiam nu mai postam pe forum si prin eleganta nu ma refeream la 5 linii de cod ..... ci la o rezolvare mai pe intelesul meu . De acu nu va mai cer ajutorul pe forum o sa ma chinui sa rezolv o problema singur .

De foarte multe ori nu exista decat o singura rezolvare pentru 100 de puncte. In cazul de fata aceasta rezolvare e postata mai sus :). Daca ai fi formulat de la inceput ceea ce doresti, poate ai fi obtinut: o explicatie mai detaliata a rezolvarii.

wefgef : "Incearca sa rezolvi probleme mai usurele de dinamica si dupaia reintoarce-te al aceasta "

offtopic: Ai putea sa imi zici niste ex de pr de nivelul meu ?

O sa implementam in curand taguri pentru probleme :). Astfel vei putea decide singur ce prb sa rezolvi ;)

Poate sa imi spuna si mie cineva cat sunt nr. puternice cu nr. de ordine 164,165 si 180?
Nu imi merg ultimele 2 teste...am facut cu nr. mari.

n=164 => 4488062423933088000
n=165 => 6133685312708553600
n=180 => 184010559381256608000

Voi ati tinut numere mari la problema asta ? Ca din cate vad de pe la N = 160 iese din long long.

Da.