519 Modulo

[•DITzoneC]

Aici puteţi discuta despre problema Modulo.

[•Dastas]

Nu e cam mult o secunda la problema asta?

[•DITzoneC]

Limita a fost micsorata la 0.1. Solutiile au fost reevaluate.

[•coderninu]

care e faza cu testul 7 ?. iau wa la el.
Idee : a%=c, b%=c; rez=1; for (i=1; i<=b; i++) rez=(rez*a)%c; si apoi afisez rez.
am crezut ca nu imi intra in tipuri standard, am bagat si nr mari , am incercat si pe long long si cu long double( cu conversii la fiecare pass), si tot la 90 pct ajunge.

b nu poate fi e sa zic sa nu imi intre deloc in for, si chiar daca ar fi fost 0 tot ar da rez bun ca ar ramane rez==1;

ma scoate din mintzi  . pls help

[•skyel]

pt a=4, b=4, c=4 iti afiseaza 1, iar rez e 0...deci e doar o coincidenta ca iei atat de mult, deoarece (a^b)mod(c) nici in o mie de ani nu va fi (a mod c)^(b mod c), adica principiu pe care spui tu ca te bazezi

[•coderninu]

stiu ca e o coincidentza, prima data cand am trimis sursa care facea pana la b mod c m-am si mirat ca am luat 70, apoi am bagat long long si am luat 90 si am crezut ca o fi bine.am lasat pana la b prima data si iau 60 pct si 4 tle. oricum algoritmul meu nu e bun. imi poti da ceva indicatii cum se rezolva?

[•DITzoneC]

Cea mai la indemana metoda este sa te gandesti cum poti calcula a^b cunoscand a^b/2. Apoi pentru calculul lui a^b/2 aplici acelasi rationament.

[•coderninu]

Ms de ajutor.Am luat pana la urma 100 .

[•ciprianf]

Pf...care poate sa-mi explice mai clar principiul cu care rezolv problema asta...ca nu inteleg...

[•astronomy]

Exact cum a spus Ditzone mai sus. Vrei sa calculezi a^b, daca b este impar a^b=a^b-1*a, altfel a^b=a^b/2*a^b/2. Din cauza ca b`ul se tot imparte la 2 complexitatea e logaritmica.

[•Tabara]

Pf...care poate sa-mi explice mai clar principiul cu care rezolv problema asta...ca nu inteleg...

si sa nu uiti sa faci % C la fiecare pas pentru ca (A*B) % C = (A%C)*(B%C) 

[•stef2n]

si sa nu uiti sa faci % C la fiecare pas pentru ca (A*B) % C = (A%C)*(B%C) 

(A*B)%C = ((A%C)*(B%C))%C

[•Tabara]

si sa nu uiti sa faci % C la fiecare pas pentru ca (A*B) % C = (A%C)*(B%C) 

(A*B)%C = ((A%C)*(B%C))%C

[•zalman]

nu stiu ce are...am facut problema in cel mai simplu mod...am ridicat pe A la puterea B si apoi am facut modulo...si iau o pct 
pls..help

[•Florian]

Daca mai intai calculezi A^B, si apoi, la sfarsit faci modulo, sa stii ca sigur nu iti va da corect. Gandeste-te la limitele lui A si B, si, apoi, gandeste-te pe ce tip de date intra un numar (cica enorm de mare) care e A^B? Ideea e sa faci modulo la fiecare pas [probabil ca ai rez=rez*A, modifica cu rez=(rez*A)%C ). Oricum, solutia asta nu iti aduce punctajul maxim. Trebuie sa faci in O(log(B)). Vezi ce s-a scris pe topicul asta. 

[•Robybrasov]

este necesar lucrul cu numere mari? vad ca poate avea multe cifre rezultatul.

[•cos_min]

Se poate fara numere mari.

[•Robybrasov]

da, m-am prins  restul este intotdeauna mai mic decat numarul la care se imparte, adica mai mic de 50.000

[•HoriaClement]

Imi zice si mie cineva ce e gresit la pb....iau o p.

[•DITzoneC]

Dupa cum iti zice si evaluatorul ai o eroare de compilare. Tu nu iti testezi problemele pe calculatorul tau ?
Dupa declaratia p:longint pune ;

[•toni2007]

Tu te astepti ca a la puterea b  sa iti intre in longint? macar pune si tu in64 (parca asta e echivalentul lui long long in pascal) da oricum nu cred ca iti ia macar un test

Cod:

for i:=1 to b do
             p:=p*a;
         k:=p mod c;

tu aici mergi cu i de la 1 la b si faci ceva gen p=a^b nu o sa iti intre in longint pt a si b mai mari de 15 uite-te si tu pe topicul asta poate gesesti o rezolvare mai buna

[•HoriaClement]

Mi-au mers toate testele...aloooo...da..nu vrea...si ce vrei sa-mi zici tu acolo cu longu'?

[•toni2007]

ce sa vrea? din cate vad ai eroare de compilare...

[•HoriaClement]

ce eroare...mie-mi merge
 

[•toni2007]

http://infoarena.ro/monitor?user=HoriaClement

eu vad ca pe problema modulo ultimele 3 evaluari au eroare de compilare