последняя ненулевая цифра факториала

[Пашка]

Подскажите опытные товарищи, как быстро найти последнюю ненулевую цифру n! если я знаю последнюю цифру (n-1)!
n - от 1 до миллиона

В общем задача выглядит так: вводится k (от 1 до 1000), затем вводятся k строк, в каждой из которых число от 1 до миллиона.
Нужно вывести в ответе k строк с последней ненулевой цифрой факториалов чисел.

Саму задачу для нахождения последней цифры одного числа я написал так
var
n, k, s, t, i, j : integer;
begin
read(n);
k := n div 5;
s := 0;
while k > 0 do
begin
s := s + k;
k := k div 5
end;
t := 1;
for i := 2 to n do
begin
j := i;
while j mod 5 = 0 do j := j div 5;
while (s > 0) and (j mod 2 = 0) do
begin
j := j div 2;
s := s-1;
end;
t := t*(j mod 10) mod 10;
end;
write(t);
end.
Она работает, но если переделать ее так, чтобы вводились несколько чисел, и все ввести достаточно большие, то она не проходит по времени, а нужно уложться в 1 секунду, это и навело на мысль о создании массива

[B_N]

Ну так выбирайте из (n-1)! и n все младшие разряды, пока не появится [не нуль] и перемножайте между собой. Останется найти первую ненулевую в этом коротком произведении.

[Пашка]

так ошибка получается, кажется когда умножаешь на 5 - уже нужны не 1, а 2 последние цифры

а потом и двух не хватает

[B_N]

Прошлый раз написал неправильно, поправляюсь - число нулей в конце факториала может быть максимум на единицу больше, чем сумма нулей на конце (n-1)! и n. И то, только в случае двойки и пятерки - иначе равно.

[Пашка]

можно с тобой в аське пообщаться?

[B_N]

Вспомнил, кажется. Последняя ненулевая цифра n*(n-1)!, это последняя ненулевая цифра произведения чисел, составленных из двух последних ненулевых цифр каждого множителя. О как. нуждается в проверке потому, как сейчас доказывать неохота.

[alexBlack]

B_N, позволь, переведу:

var i, C:integer;
    A:array[1..1000000] of byte;
begin
   k := 1;
   for i:=1 to 1000000 do begin
      C := i;
      while C mod 10 = 0 do C := C div 10;
      k := k * C;
      while k mod 10 = 0 do k := k div 10;
      k := k mod 100000;
      A[i] := k mod 10;
   end;

Проверил. Работает.... но:
------------------------------------------------------
Утром понял, что k := k mod 100000; приводит к накоплению ошибок.
Мы отбрасываем правые знаки, но т.к. далее будет умножение на 2 и 5, мы получим лишний ноль в конце и эти знаки нам понадобятся.

Приведу другой вариант. Будем считать двойки и пятерки в разложении каждого числа.

   k25 := 0;
   k := 1;
   for i:=1 to 1000000 do begin
      C := i;
      while C mod 2 = 0 do begin
         C := C div 2;
         inc(k25);
      end;
      while C mod 5 = 0 do begin
         C := C div 5;
         dec(k25);
      end;
      k := k * C mod 10;   // последняя цифра без 2^k25

      if k25 < 0 then begin
         raise exception.Create('error'); 
      end;
      // Двоек в разложении всегда больше
      // Требуется не более 8 двоек
      // чтобы перекрыть все пятерки, которые появятся в дальнейшем
      // Лишние двойки можно сразу включить в произведение
      while k25 > 8 do begin
         k := k * 2 mod 10;
         dec(k25);
      end;

      // Оставшиеся двойки
      n := k;
      for j:=1 to k25 do n := n*2 mod 10;
      B[i] := n;
   end;

Разница с предыдущим вариантом начинается с 9375!