Pagini recente » Cod sursa (job #1068278) | Cod sursa (job #548755) | Cod sursa (job #1646853) | Cod sursa (job #2489468) | Cod sursa (job #387217)
Cod sursa(job #387217)
const max5=13;
var p5:array[0..max5]of longint;
p,n:longint;
i,m:byte;
procedure crearep5;
var i:byte;
begin
p5[0]:=1;
for i:=1 to max5 do p5[i]:=p5[i-1]*5;
end;
{procedure verifica;
begin
p:=0;
for i:=1 to max5 do p:=p+n div p5[i];
writeln;
write(p);
end;}
begin
{
Rezolvare (fara documentare):
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Numarul de zero-uri de la sfarsitul unui numar n este dat de numarul de
perechi (5,2) sau (2,5) din despartirea in factori primi a lui n;
Exemplu:
n=120000
120000=2^6*3^1*5^4
Sunt 4 factori de 5 si 6 factori de 2 => 4 perechi (5,2) =>
n are 4 zerouri la sfarsit (si chiar are)
Adica numarul de zerouri este dat de minimul de aparitii dintre
factorul 5 si factorul 2 in descompunerea in factori primi a lui n.
Fiind dat un n, pentru numarul n! este chiar mai usor sa aflam cate
zerouri are la sfarsit! Stiind ca n!=1*2*3*...*n trebuie sa aflam cate
perechi (5,2) exista in descompunerea lui n! in factori primi.
n! se imparte la 2 de mai multe ori datorita existentei factorilor 2, 4, 6,
8, 10 ... (4=2*2; 6=2*3; 8=2*2*2; 10=2*5) => putem afla numarul de factori 2
in descompunerea lui n! in factori primi.
n! se imparte la 5 datorita existentei factorilor 5, 10, 15 ... .
Pentru n! numarul de aparitii a lui 5 ca factor prim este mai mic decat
numarul de aparitii a lui 2 ca factor prim. Prin urmare, numarul de zerouri
este dat de numarul de aparitii a lui 5 in descompunerea lui n! in factori
primi.
Problema noastra este ca primim numarul de zerouri care trebuie sa-l aiba
n!, iar noi trebuie sa aflam acel n. Asa ca formez n-ul din mers. Probabil
exista si o alta metoda mai eficienta decat a mea, dar cred ca rezolvarea
se bazazeaza pe cele spuse inainte.
De fapt, vreau sa observ la cate teste nu ma incadrez in timp. (dar trebuie
sa fie si rezolvarea corecta).
}
crearep5;
assign(input,'fact.in');
reset(input);
assign(output,'fact.out');
rewrite(output);
{p < 100 000 000}
read(p);
m:=max5;
n:=p*5;
while(p5[m]>n)do dec(m);
n:=0;
while p>0 do
begin
n:=n+5;
i:=2;
while(i<=m)and(n mod p5[i]=0)do inc(i);
p:=p-i+1;
end;
if p<0 then write('-1')
{
0!=1 este cel mai mic numar care are 0 cifre de zero la sfarsit, dar ni se
cere un numar strict pozitiv => alegem 1!
}
else if n=0 then write('1')
else write(n);
{verifica;}
close(output);
close(input);
end.