332 Puteri

[•DITzoneC]

Aici puteţi discuta despre problema Puteri.

[•k_ounu_eddy]

De ce problema asta era cea mai grea?Mie mi s-a parut cea mai usoara.Luai toate perechile de elemente,si le faceai suma in puterilor.De ex aveai 2 elemente:
2 3 4
3 2 1
Si iti dadea elementul:
5 5 5.Apoi luai fiecare 2 puteri si faceai modulo,si daca era 0=>elementul se poate scrie ca o putere. In ex nostru 5%5=0.Numarul se poate scrie ca (2*3*5 )^5.
Alt exemplu:
2 4 0
1 2 0.
Dadea elementul:
3 6 0.6%3==0.Elementul se poate scrie ca (2*3^2)^3.
E ceva gresit in solutia mea.Se incadreaza in timp?

[•CezarMocan]

Din cate am inteles eu solutia ta e O(n^2). Cu o asemenea solutie luai 40 de puncte cu TLE pe 6 teste(asa au facut-o majoritatea in timpul concursului). Decat sa te complici cu modulo si faze faci cmmdc la cele 3 numere din pereche .

[•k_ounu_eddy]

Pai cum fac sa obtin 100 de puncte,ca ai zis ca o(n^2) ii prea mare

[•CezarMocan]

http://infoarena.ro/preoni-2007/runda-3/solutii.
Aici sunt scrise solutiile tuturor problemelor ce au fost la preONI 2007 runda 3, inclusiv Puteri. (cauta si tu mai mult pe site inainte sa intrebi... )

[•k_ounu_eddy]

Asa voi face.

[•geniucos]

Numerele sunt pana la 64 sau 2^64?

[•danalex97]

Cum faci problema asta de 100 de puncte cu noua limita de timp ?  Se poate mai repede decat cu Pinex ?