Care e cel mai rapid mod de a testa daca un numar e patrat perfect?
Eu fac asa:
citeste n
r=sqrt(n);
daca r*r==n scrie "Patrat perfect!\n"
altfel scrie "Nu e patrat perfect!\n"
Ma gandesc ca o cautare binara ar fi prea inceata:
int pas, i, n;
citeste n
pentru pas=1;pas*pas<=n;pas<<=1;
pas>>=1;
daca pas*pas==n scrie "Patrat perfect!\n"
altfel pentru i=pas;pas;pas>>=1
daca (i+pas)*(i+pas)<=n
i+=pas;
daca i*i==n scrie "Patrat perfect!\n"
altfel scrie "Nu este patrat perfect!\n"
M-am gandit si asa: Diferenta dintre 2 patrate perfecte consecutive este un numar impar.
(n+1)
2-n
2=n
2+2n+1-n
2=2n+1.
De unde verific asa:
int i, p;
pentru i=p=1;p<n;p+=((i<<1)|1),++i;
daca p==n scrie "Patrat perfect!\n"
altfel scrie "Nu este patrat perfect!\n"
Prima solutie are complexitate O(1), dar ma gandesc ca dureaza prea mult din cauza functie sqrt(), iar a doua si a treia O(log n), respectiv O(sqrt(n)).
Nici una nu mi se pare suficient de rapida, mai ales ca iau TLE la o problema de pe TIMUS.
Ma poate ajuta cineva cu vreo imbunatatire?