infoarena

Aici puteţi discuta despre problema Suma divizorilor (http://infoarena.ro/problema/sumdiv).

Puteti sa imi ziceti cat va da pe testele astea:

17297398 38883838
47468734 37682100
50000000 50000000
12345678 48765012

Thanx

Daca nu am busit cand am bagat datele ar trebui sa dea asa

nu stie cineva cum pot calcula restu impartirii la 9901 a unui produs de mai multe progresii geometrice? ... presupun ca un algoritm liniar nu intra in timp ... deci in timp logaritmic  ....  la ce ma ajuta faptul ca 9901 ii prim ?

O problema foarte asemanatoare  a fost propusa la preONI, articolul cu explicatii este aici: http://info.devnet.ro/articole.php?page=art&art=85&artpage=5
citeste articolele ;)

si eu am o nelamurire asemanatoare... adica....cum calculez ((A^B-1)/(A-1)) modulo N ?...fara a efectua inpartirea?

Avand in vedere faptul ca N=9901 este prim poti transforma impartirea in inmultire... Adica pentru orice X exista un X' astfel incat
A/X = A*X' modulo N(oricare ar fi A). Acest X satisface proprietatea X*X'=1 (mod N) adica este simetricul lui X in corpul (Z_n,*). Draguta algebra de a 12-a :)

adica...tot ce traba sa fac e sa gasesc inversu numitorului?...si inmultesc cu el?...si fac modulo N?...

ai vazut link`ul de mai sus in care se explica exact cum se face chestia asta?  :-'

Am citit topicul asta, insa nu prea m-am lamurit. Ati putea sa-mi spuneti cum pot calcula E=a^0+a^1+a^2+ ... +a^x  in timp logaritmic? Stiu cum se calculeaza logaritmic a^y, insa nu vad cum m-ar putea ajuta...

Pai E ala este o progresie geometrica. Nu stii formula pentru progresii geometrice?

Mda...am uitat ca mai exista si formula pt suma primilor n termeni ai unei progresii geometrice... Ce face timpul din oameni... Multumesc mult!  :thumbup:

Sau poti aplica metoda folosita la problema Calcul. (vezi in articolul asta (http://infoarena.ro/preoni-2006/runda-4/solutii))

Din ce am inteles din articolul ala:

In loc sa calculez (A^(B+1)-A) / (A-1), trebuie sa calculez [ (A-1) ^ (phi(9901)-1) ]* (A^(B+1)-A).
Deci in loc sa impart la (A-1) si sa aplic dupaia %9901, inmultesc cu inversul lui, care e de fapt (A-1)^(phi(9901)-1), putand aplica "%9901" la fiecare pas.
Am inteles bine?  Ca nu prea imi da corect...  :-k

Vad ca ai TLE-uri la ultima sursa trimisa, nu WA-uri :).

Din cate imi aduc aminte, parca era un caz particular, cand A = 1. Nu mai stiu exact.

La ultima sursa trimisa am facut in mod liniar... [ un fel de brute force ] . Nu imi da corect pe testele mele, daca fac cum scrie in articolul ala. Nu imi dau seama care e problema...  :? phi(9901)=9900, nu?

Iti da bine atunci cand:

- A = 1
- B = 0
- A = 9901
- B = 1

?

pt a=1 si b=0 imi da bine. Dar pt a=9901 si b=1 imi afiseaza 0.

Am ceva de genu:

 sol = ( p u t e r e ( i - 1 , 9901-2 )  *( p u t e r e ( i , b * r + 1)  - i ) ) % 9901;
 P = ( P * s o l ) % 9901;

unde P e solutia finala, iar "i" e factorul prim care apare la puterea "r" in factorizarea lui A.
Functia "putere(x,y)" imi returneaza x^y in O(log(y)),facand la fiecare pas (inmultire) operatia "%9901".

Care e greseala?  :sad:

Poti sa iti iei testele de la ONI 2002 sa iti verifici (vezi Downloads).

Ideea e ca nu imi da bine nici pe testele mele. Nu inteleg ce gresesc. Factorizarea o fac sigur bine, ridicarea x^y e sigur buna, insa nu stiu daca e bine cum aflu suma aia (1+a^1+..+a^b) . E bine ce am scris cu un post mai sus?

Nu faci bine suma, e (a^(b+1)-1)/(a-1)

Ar trebui modificat si in articolul cu solutii pt "Calcul"... asta se intampla daca ai prea mare incredere in articole..  Multumesc de ajutor.
Acum imi iese, insa iau niste incorecturi. Problema apare atunci knd [a^(b+1)]%9901==0. Atunci knd scad 1, imi da -1, si imi iese numar negativ. Deci atunci knd a-ul este un multiplu a lui 9901. Cum as putea sa rezolv?

Ar fi bine sa citesti cateva notiuni de teoria numerelor. Uita-te in Cormen :).

-1 congruent cu 9900 modulo 9901.

Articolul n-are nimic gresit. Daca te uitai atent vedeai ca la Calcul suma incepe de la A^1, iar aici iti trebuie de la A^0, d-aia difera un pic formula.

Se poate uita cineva pe sursa mea ? imi da bine, doar ca iau 10 puncte.
Ms anticipat.

Eu nu imi dau seama,de ce iau numai 30 de puncte?Ce-i gresit in rezolvare?Mie imi da cum trebuie...

http://infoarena.ro/job_detail/325599   ???

Tu faci pow(a,b), a si b fiind 50 de milioane. Nu iti vor intra in nici un tip de date. De acolo iei wa.

long int tine valori pana la 2³². Daca a si b ajung la 50 milioane, nici macar long long nu poate retine a^b. Trebuie sa folosesti opreatiile cu numere mari (un numar retinut ca vector de cifre). Uite-te aici (http://infoarena.ro/multe-smenuri-de-programare-in-cc-si-nu-numai) pentru mai multe detalii despre asta.

In orice caz, rezolvarea ta nu este de 100 ;)

Nu intra in timp.

Am abordat problema in alt mod, de la ultimul post in acest topic am mai invatat cate ceva. :)

Am citit articolul (http://infoarena.ro/preoni-2006/runda-4/solutii) si am facut intocmai, am calculat intr-o functie (AB+1-A) / (A-1) . Iau doar 10 puncte pe sursa  (http://infoarena.ro/job_detail/333995) .

La multe teste nu se incadreaza in timp, totusi din cate am citit acesta pare cel mai bun algoritm. Ce am gresit ?  :baby:

In urma cu 2 posturi ti-a explicat cotizo ca nu poti calcula A la puterea B cu un for si sa il retii intr-un int/long/long long.

Salutare!

Articolul de mai jos nu mai este activ; are cineva alta legatura care sa prezinte informatiile din articol  sau macar ceva similar ce ar putea ajuta la rezolvarea problemei?


http://info.devnet.ro/articole.php?page=art&art=85&artpage=5