188 Suma divizorilor

[ditzone]

Aici puteţi discuta despre problema Suma divizorilor.

[•pauldb]

Puteti sa imi ziceti cat va da pe testele astea:

17297398 38883838
47468734 37682100
50000000 50000000
12345678 48765012

Thanx

[•vladcyb1]

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

Cod:

2161
5304
7544
5200

[•alex_prg]

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 ?

[u-92]

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

[•cristy]

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

[ditzone]

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

[•cristy]

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

[u-92]

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

[•Florian]

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...

[•wefgef]

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

[•Florian]

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

[•DITzoneC]

Sau poti aplica metoda folosita la problema Calcul. (vezi in articolul asta)

[•Florian]

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... 

[•wefgef]

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.

[•Florian]

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?

[•wefgef]

Iti da bine atunci cand:

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

?

[•Florian]

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? 

[•wefgef]

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

[•Florian]

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?

[•astronomy]

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

[•Florian]

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?

[•wefgef]

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

-1 congruent cu 9900 modulo 9901.

[•domino]

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?

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.

[•floflow]

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