dZnam deka mozda zamaram, ama svarno ne sfakam zaso ova paga na 8 primeri:
var i,j,o,s:longint;
m:longint;
function f(o,s,m:longint):longint;
begin
o:=o mod m;
if s=0 then f:=1 else
if s=1 then f:=(o mod m) else
if (s mod 2=0) then f:=(( sqr ( f(o,trunc(s/2),m))) mod m)
else f:=((o*sqr(f(o,trunc(s/2),m))) mod m);
end;
begin
read(o,s,m);
writeln(f(o,s,m));
end.
Mozda postoji sansa da ti
else f:=((o*sqr(f(o,trunc(s/2),m))) mod m); daje overflow.
probaj recimo
else f:=((o*(sqr(f(o,trunc(s/2),m)) mod m) mod m);
Ovo je samo nagadjanje, ali javi da li je pomoglo :) istina je da tebi funkcija vraca po mod m, ali ti kvadriras, pa se mozda tu negde prekoraci (3999^3 > 2^31 - 1).
Inace, algoritam mi deluje sasvim ok.
Koriscen je algoritam za efikasno stepenovanje dva prirodna broja koji radi na sledecu foru:
n^k=(n^(k/2))^2 ako je k parno
n^k=n*(n^((k-1)/2))^2 ako je k naparno
evo moje rekurzije ako moze da ti pomogne.
Fora je i u tome da se cesto radi mod m.
long int stepen (long int o,long int s,long int m){
o=o%m;
long int x;
if(s==0){return 1;}
if(s==1){return o;}
if(s%2==0){x=stepen(o,s/2,m)%m;
x=(x*x)%m;
return x;}
else {x=stepen(o,s/2,m)%m;
x=(x*x)%m;
x=(x*o)%m;
return x; }
}
@todosijevic
Hvala za algoritam, pomogao mi je pri resavanju jer sam imao problem sa ogranicenjima :)
Pozdrav, Aleksandar.
ja owaj zadatak resim,test primeri mi rade,a z-trening nece da primi zadatak...zna li neko u cemu je problem ???...
@Dumbe93:
Ogi , pogledao sam ti source. Izbaci one komentare tipa "Unesi brojeve" , "Rezultat je", etc. Ovaj zadatak ne mozes da resis tako sto cjes preko for petlje da izracunas o^s pa da izbises (o^s) mod m, jer necje procji vremensko ogranicenje. Probaj da iskorisis ovu funkciju iznad. ;) Ispricacju ti sve u skoli. ;)
