Pagini recente » Diferente pentru blog/problema-saptamanii-vanatori intre reviziile 4 si 3 | Clasamentul arhivei Infoarena Monthly | Diferente pentru blog/infoarena_in_2008_articole intre reviziile 10 si 9 | Diferente pentru blog/s-a-incheiat-unirea-2007 intre reviziile 4 si 3 | Diferente pentru autumn-warmup-2007/solutii/runda-3 intre reviziile 36 si 35
Nu exista diferente intre titluri.
Diferente intre continut:
Algoritmul folosit in rezolvarea pentru $100$ de puncte este Miller-Rabin. Este un algoritm probabilistic care verifica primalitatea unui numar in complexitate $O(c*log Nr)$, unde c este numarul de baze folosite pentru verificare.
Dorim sa verificam daca numarul Nr este prim. Primul pas care trebuie efectuat este acela de a-l scrie pe Nr-1 ca numar de forma $2^s^*d$, unde s trebuie sa fie maxim. Pasul urmator este sa verificam 2 relatii:
1. $a^d^ mod n ≠ 1$
2. <tex> a^{2^r*d} </tex> $mod n ≠ -1$, pentru $0 ≤ r ≤ s-1$
2. <tex> a^{2^r*d} </tex> $mod n ≠ -1$
h2. 'Kcity':problema/kcity
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
