h2. 'Ubercool':problema/ubercool

**Solutia 1**
 

Este clar ca exponentul unui număr de forma $a^b^$, unde $a$ este prim şi $b$ este mai mare ca $2$, nu poate depăşi 60, deoarece $2^60^ > 10^18^$, iar baza nu depăşeşte $10^9^$. Atunci putem fixa exponentul, iar pentru un exponent fixat, trebuie sa calculam radical de ordinul respectiv din numărul iniţial. Daca acesta este un întreg, şi este şi prim, răspunsul este afirmativ. Daca am parcurs toţi exponenţii şi nu am găsit un radical întreg şi prim, răspunsul este negativ.
Pentru a calcula radical de ordin $N$ dintr-un număr $X$ se putea alege căutarea binara pentru a evita erorile de precizie, sau se putea alege varianta cu $pow (X,1.0/N)$, dar în acest caz trebuia atenţie la precizie.

**Solutia 2**
 
Este clar ca baza unui numar pentru un exponent mai mare sau egal ca 3 este mai mica decat 1.000.000. Astfel vom preprocesa toate numerele prime de la 2 la 1.000.000 cu ajutorul 'Ciurului lui Eratosthenes':problema/ciur. Dupa ce avem fiecare numar prim vom calcula puterile lui (mai mici decat 10^18) si vom verifica in lista celor N numere daca se regaseste. Pentru o cautare optima se vor pastra cele N numere intr-un 'Hash':problema/hashuri.
 
In acest mod vom gasi toate solutiile pentru un exponent mai mare sau egal ca 3. Pentru fiecare numar care nu a fost gasit ca fiind ubercool se va cauta o solutie de forma $a^2^$, adica se va calcula radicalul, se va verifica daca este numar intreg si prim in acelasi timp. Pentru verificarea primalitatii se poate folosi algoritmul de pseudoprimalitate Miller-Rabin sau direct algoritm naiv in complexitate $O(sqrt(N))$.
 
Aceasta solutie este optima si pentru un N de pana la 1 milion (cu precizarea ca necesita algoritmul Miller-Rabin pentru determinarea primalitatii unui numar), deoarece preprocesarea numerelor ubercool pentru b >= 3 este rapida si independenta de numarul N.
 

h2. 'Curatenie':problema/curatenie
Problema cere sa găsim un arbore binar având la dispoziţie parcurgerile lui inordine şi preordine. Parcurgerea inordine este: $STÂNGA RĂDĂCINA DREAPTA$ iar cea în preordine este $RĂDĂCINA STÂNGA DREAPTA$.