Cod sursa(job #387217)

Utilizator mimarcelMoldovan Marcel mimarcel Data 27 ianuarie 2010 08:17:09
Problema Factorial Scor 60
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.4 kb
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.