Ubercool

[•savim]

Aici puteti pune intrebari la problema Ubercool de la concursul FMI No Stress 3.

[•misino]

de ce imi afiseaza Killed by signal 8(SIGFPE).
desi nu am depasit memoria si nu citesc numere prea mari
Timpul de executie este 0 pt fiecare test

[•wefgef]

Cam jeg cu erorile de precizie. Mergea precizata in enunt precizia care trebuie folosita.

[•DraStiK]

Cam jeg cu erorile de precizie. Mergea precizata in enunt precizia care trebuie folosita.

Merge problema si folosind long long, fara a avea nevoie de precizie.

[•Mihai22e]

cum se rezolva aceasta problema?

[•Vman]

pentru fiecare exponent se cauta binar baza astfel incat pow(baza, exponent) = N. apoi se verifica daca baza este numar prim. Asta se poate face optim cu testul de primalitate miller rabin, dar in cazul de fata intra si solutia naiva in sqrt(baza), adica iei toate numerele pana la radical si vezi daca vreunu divide baza

[•Mihai22e]

asta fac si eu..iau pe rand toti exponentii de la 2 la 60 (pot sa am 2^59 < 10^18) si cu cu ajutorul cautarii binare caut baza. daca am gasit o  baza a, astfel incat a^b = x (numaru' dat pentru acel test), verific daca a este prim; aici am 2 cazuri: a < 100 000 (verific in vectorul creat cu ajutorul ciurului) si a >= 100 000 (caut in vectorul v in care am numai numere prime < 100 000 daca exista vreun numar v astfel incat a % v = 0 => nu este prim, iar in caz contrar, este prim). nu mi-a intrat decat pe un test, restul wa

[•danalex97]

testul de primalitate miller rabin

Imi dai , te rog , un link despre asa ceva ?

[•SpiderMan]

Uite aici.

[•Mihai22e]

multumesc de ajutor, o sa incerc si aceasta metoda, dar vreau sa stiu ce este gresit in rationamentul meu

[•danalex97]

10x. 

[•DraStiK]

multumesc de ajutor, o sa incerc si aceasta metoda, dar vreau sa stiu ce este gresit in rationamentul meu

Rationamentul tau este in principu bun, doar ca implementarea nu prea e buna. De exemplu, sursa ta pentru numarul 115651132813084969 nu da un raspuns corect.

115651132813084969 este 340075187^2, deci e ubercool, iar sursa ta nu e deacord.

[•Mihai22e]

asa este, in functia in care compar a^b cu x, imi depaseste unsinged long long int. mersi drastik

[•darren]

pentru fiecare exponent se cauta binar baza astfel incat pow(baza, exponent) = N

Sau, mergea foarte bine si chestia asta: baza = pow(N, 1.0 / i).

[•S7012MY]

pentru fiecare exponent se cauta binar baza astfel incat pow(baza, exponent) = N

Sau, mergea foarte bine si chestia asta: baza = pow(N, 1.0 / i).

Eu am incercat asa si nu mi-a mers. faceai vreun artificiu ?

[•darren]

pentru fiecare exponent se cauta binar baza astfel incat pow(baza, exponent) = N

Sau, mergea foarte bine si chestia asta: baza = pow(N, 1.0 / i).

Eu am incercat asa si nu mi-a mers. faceai vreun artificiu ?

Cod:

double now = pow((long double) N, 1.0 / i);
long long inow = now;
if (pow((long  double) inow, i) == N)
    ...

Nu cred ca era nevoie de long double, dar am pus asa doar ca sa ma asigur ca merge.

[•geniucos]

Imi puteti da si mie niste teste mai mari,va rog?Pentru ca sa verific ca un numar n<=10^9 este prim am tinut toate numerele prime pana in 31624 si l-am impartit pe rand la toate<=sqrt(n).IIau 0 puncte cu 3TLE si 7 WA.
Multumesc anticipat.
Si inca ceva cat ar trebui sa dea pentru 0,respectiv 1?

[•soriyn]

Nu am rezolvat problema dar in timp nu are cum sa iti intre. Iar wa e normal sa iei pentru ca n<=10^18, deci trebuie sa retii toate numerele prime <= 10^9 si nu prea ai cum sa faci asta. Metoda ta de rezolvare nu e buna. Pentru 0 si 1 raspunsul ar trebui sa fie "NU"

[•geniucos]

Eu am
n=a^b cu b>=2 =>a<=10^9.Pentru a verifica daca a este prim am luat totate numerele prime<=sqrt(a)si daca a se imparte la vre unul din ele atunci nu este prim altfel este.Nu cred ca este ceva gresit in rationamentul meu.Sau daca da as vrea un test sau mai multe sa vad de ce.
Nu ma astept la 100 de puncte dar vreau sa vad ce am gresit de iau WA.
Daca nu este niimic gresit in rationamentul meu atunci ati putea sa imi dati niste teste mai mari sa imi gasesc greseala.
Multumesc anticipat.

[•DraStiK]

Cod:

input:
10
66078623738400
418121490257280
1024192009
811864507620600
289852172683465681
1101642481
742726009
140802626764800
12400864
22968504

Cod:

output:
NU
NU
DA
NU
DA
DA
DA
NU
NU
NU

[•geniucos]

Multumesc foarte mult,in special pt testul 5.Am luat 100 cu ideea aia.