Найти количество нулей на конце n!

@GreenFoxer · Регистрация: 26.04.2015

Author24 — интернет-сервис помощи студентам

Здравствуйте, я готовлюсь к олимпиаде и мне дана задача: Найти количество нулей на конце n! (n факториал). n<=10^9. Но вот проблема, мое решение слишком долго выполняется для больших чисел и поэтому превышает лимит по времени выполнения. Можно ли как то его изменить, чтобы оно выполнялось быстрее? Вот мое решение:

Pascal

var b,n,i:longint;
s:real;
begin
read(n);
b:=0; s:=0;
for i:=1 to n do
begin
if (i mod 5 = 0) then
begin
b:=i;
while b mod 5 = 0 do
begin
b:=b div 5;
s:=s+1;
end;
end;
end;
write(s:20:0);
end.

@GreenFoxer · 05.02.2016, 13:03 **[ТС]**

Не спорю. Я и готовлюсь. Так как же мне все таки нужно переделать мое решение?

@SpBerkut · 05.02.2016, 13:05

Не по теме:

Мистика. Где моё сообщение? Я же уже писал ответ.

Pascal

S := 0;
Readln(N);
while N > 5 do
begin
  S := S + N div 5;
  N := N div 5;
end;

@bormant · 05.02.2016, 13:07

На одно деление короче:

Pascal

S := 0;
Readln(N);
while N > 5 do
begin
  N := N div 5;
  S := S + N;
end;

@GreenFoxer · 05.02.2016, 13:09 **[ТС]**

Спасибо, помог)

@Constantin Cat · 05.02.2016, 13:11

Pascal

1	n div 5+n div 25

@SpBerkut · 05.02.2016, 13:16

Сообщение от Constantin Cat

n div 5+n div 25

Мон шер... И сколько нулей в конце 1000! насчитает такая формула?

Сообщение от bormant

На одно деление короче:

Это да.

@Constantin Cat · 05.02.2016, 16:45

Сообщение от SpBerkut

Мон шер... И сколько нулей в конце 1000! насчитает такая формула?

249

Сообщение от GreenFoxer

Можно ли как то его изменить, чтобы оно выполнялось быстрее?

Можно, исправленный вариант:

Pascal

var
  a,b,c:longint;
begin
  write('N:=');
  readln(a);
  b:=5;
  c:=0;
  while a>b do
    begin
      c:=c + a div b;
      b:=b * 5;
    end;
  write('C:=',c);
end.

на 10000! совпало.

@Puporev · 05.02.2016, 18:23

Сообщение от SpBerkut

И сколько нулей в конце 1000! насчитает такая формула?

Сообщение от Constantin Cat

249

А нифига

@GreenFoxer · 05.02.2016, 21:18 **[ТС]**

Почему то прошло не все тесты...

Сообщение от Constantin Cat

Можно, исправленный вариант:

Pascal

var
  a,b,c:longint;
begin
  write('N:=');
  readln(a);
  b:=5;
  c:=0;
  while a>b do
    begin
      c:=c + a div b;
      b:=b * 5;
    end;
  write('C:=',c);
end.

@Sergio Leone · 06.02.2016, 00:01

Сообщение от GreenFoxer

Почему то прошло не все тесты...

я, конечно, чего-то не понимаю, но я считал, что 5! = 120
(один ноль в конце есть).
а код выдаёт ноль нулей...

может быть, нужно нестрогое равенство:

Pascal

begin
  S := 0;
  Readln(N);
  while N >= 5 do
  begin
    N := N div 5;
    S := S + N;
  end;
  WriteLn(s)
end.

@GreenFoxer · 06.02.2016, 00:09 **[ТС]**

Сообщение от Sergio Leone

может быть, нужно нестрогое равенство

ДА!!! СПАСИБО!!!

@Sergio Leone · 06.02.2016, 00:11

Не по теме:

Сообщение от GreenFoxer

ДА!!! СПАСИБО!!!

да мне, собственно, не за что! Идею (алгоритм) придумали выше (респект SpBerkut!)
я так - "мимо проходил" :)

@GreenFoxer 1 / 1 / 1 Регистрация: 26.04.2015 Сообщений: 56
	05.02.2016, 13:03 [ТС]	2
	Не спорю. Я и готовлюсь. Так как же мне все таки нужно переделать мое решение? 0

@GreenFoxer 1 / 1 / 1 Регистрация: 26.04.2015 Сообщений: 56
	05.02.2016, 13:09 [ТС]	5
	Спасибо, помог) 0

@SpBerkut Объявлятель переменных 1220 / 406 / 320 Регистрация: 24.09.2011 Сообщений: 1,265
	05.02.2016, 13:16	7
	Сообщение от Constantin Cat n div 5+n div 25 Мон шер... И сколько нулей в конце 1000! насчитает такая формула? Сообщение от bormant На одно деление короче: Это да. 0

@Puporev Почетный модератор 64300 / 47595 / 32743 Регистрация: 18.05.2008 Сообщений: 115,181
	05.02.2016, 18:23	9
	Сообщение от SpBerkut И сколько нулей в конце 1000! насчитает такая формула? Сообщение от Constantin Cat 249 А нифига Миниатюры 0

@GreenFoxer 1 / 1 / 1 Регистрация: 26.04.2015 Сообщений: 56
	06.02.2016, 00:09 [ТС]	12
	Сообщение от Sergio Leone может быть, нужно нестрогое равенство ДА!!! СПАСИБО!!! 0

@Sergio Leone
	06.02.2016, 00:11 Найти количество нулей на конце n! #13
	Не по теме: Сообщение от GreenFoxer ДА!!! СПАСИБО!!! да мне, собственно, не за что! Идею (алгоритм) придумали выше (респект SpBerkut!) я так - "мимо проходил" :) 0

Найти количество нулей на конце n!

Решение