Последняя ненулевая цифра N!

[Poma][a]

День добрый, господа! Прошу помощи при решении одной задачи (моё решение валится на 9 тесте, а попытки избавиться от ошибки не дали ожидаемого результата). Итак условие :
Требуется найти последнюю ненулевую цифру числа N! = 1*2*3*…*N.
Входные данные

Входной файл INPUT.TXT содержит единственное натуральное число N (N<=9999).
Выходные данные

В выходной файл OUTPUT.TXT выведите ответ на задачу.

Так же прилагается ссыль
Моё решение :

 var
        n, i : Integer;
        r : Int64;


begin
        assign(input, 'input.txt'); reset(input);
        assign(output, 'output.txt'); rewrite(output);

        ReadLn (n);

        r := 1;
        for i := 1 to n do begin
                r := r * i;

                while r > 100000000 do begin
                        while  r mod 10 = 0 do
                                r := r div 10;

                        r := r mod 10;
                end;

        end;

        while r > 10 do begin
                while  r mod 10 = 0 do
                        r := r div 10;

                r := r mod 10;
        end;

        if r mod 10 = 0 then
                r := r div 10;

        WriteLn (r);
end.

P.S. прошу не относить меня к разряду стедентов\школьников попрошаек, т.к. я приложил массу усилий и стараний к решению данной задачи.....
P.P.S. решаю только для себя, сдавать мне не надо, время не ограничено, но Вы сами понимаете, что нектропостингом заниматься не хочется....
P.P.P.S. и был бы ОЧЕНЬ признателен если бы Вы указали мою ошибку (уж не сочтите за наглость, я понимаю что разбираться в чужом коде не всегда приятно(мягко сказано), т.к. есть планы становиться Программистом (я бы даже сказал мечты), не буду умным, но хоть на своих ошибках поучусь!)

Заранее огромное спасибо!!!

[BDA]

В общем, вот такое решение прошло:

var
  n, i: Integer;
  r: int64;

begin
  assign(input, 'input.txt');
  reset(input);
  assign(output, 'output.txt');
  rewrite(output);
  ReadLn(n);
  r := 1;
  for i := 2 to n do
  begin
    r := r * i;
    while r mod 10 = 0 do
      r := r div 10;
    r := r mod 100000000;
  end;
  r := r mod 10;
  WriteLn(r);

end.

Объяснить четко количество нулей сходу не могу (но 9999*100000000 должно влезать в тип).
Но если оставлять только 1 цифру, то ошибка возникает точно.
Например:
112
112*15=1680 (последняя 8)
2*15=30 (последняя 3)

[ViktorR]

Я вот как подумал.
При вычислении произведения (факториала) число двоек в перемножаемых числах будет больше числа пятерок.
А произведение этих чисел (двоек и пятерок) порождает нули справа.
Если исключить такие перемножения, то результат можно достичь следующим способом:

var i, n: word;
   rez, i5: word;
    fact: int64;

BEGIN
readln(n);
fact := 1;
i5 := 0;
for i := 2 to n do begin
   rez := i;
   while (((i mod 5) = 0) AND (rez > 4)) do begin
      i5 := i5 + 1; {подсчитаем число пятерок в множителе}
      rez := rez div 5; {исключим их из умножения}
   end;
   while (i5 <> 0) do begin
      fact := fact div 2; {сократим наше произведение на такое число двоек}
      i5 := i5 - 1;  {сколько пятерок в множителе}
   end;

   fact := fact * rez; {вычисляем наше произведение}
end;
writeln('Fact: ', fact, ' Last namber: ', (fact mod 10));
END.

Так сгодится? ...

[eoln]

Решение потёр, т.к. оно такое же как у BDA

[evg_m]

При вычислении произведения (факториала) число двоек в перемножаемых числах будет больше числа пятерок.
А произведение этих чисел (двоек и пятерок) порождает нули справа.
Если исключить такие перемножения, то результат можно достичь следующим способом:

если хочется математики, то вот
1. определим функцию f(x) -последняя ненулевая цифра числа x
2. можно утверждать f(a*b) =f( f(a)*f(b) )
к примеру f(20) =f(2*10) =f(f(2) *f(10)) =f(2*1)=f(2)=2

3. введем обозначения
m -число цифр в 10-ой записи числа n. ( m<=log10(n) )
k -последняя цифра в записи числа n. (0<=k<=9)

4. тогда
f(n!) =f ( f(8**m) * f(k!) )
при желании можно еще раз применить правило 2.

немного программирования
считаем f(8**m)

r1:=1;
for j:=1 to m do r1:=(r1 *8) mod 10;

нулей в конце быть не может => проверка if r2 mod 10 =0 не требуется!

считаем f(k!)

case k of // проще посчитать один раз на бумажке
1: r2:=1;
2: r2:=2;
3: r2:=6;
4: r2:=4;
5: r2:=2;
...
9: r2:=...
end;

считаем итог

result:=r1 *r2 mod 10; (в r1 r2 есть двойки но нет ни 10 ни 5 )

[ViktorR]

Прекрасно. Мне нравится.
Это и к вопросу о том, нужна ли математика в программировании
Возьму на заметку.

Решение потёр, т.к. оно такое же как у BDA

У меня так бывает: в голове появляется своя мысль и в другую мысль уже не въезжаешь.

[evg_m]

а если еще чуть математики, то и компьютер становится почти не нужен!
f(8**1) = 8
f(8**2) = (6)4 =8*8
f(8**3) = (3)2 =4*8
f(8**4) =(1)6 =2*8
f(8**5) =(4)8 =6*8

считаем f(8**m)
case m mod 4 of
1: r1:=8;
2: r1:=4;
3: r1:=2;
0: r1:=6;
end;

в предыдущем посте при вычислении f(k!) (в написании кода) незаслуженно забыл упомянуть случай k=0

case k of
0: r2:=1; // вот так
....

итак вся программа

case m of 
1: r1:=...
....
end;
case k of
0: r2:=...
end;
result:=r1 *r2 mod 10;

при желании можно свести две таблицы (m =0..3) (k=0..9) в одну двумерную (просчитав возможные результаты их всего 40 (4Х10)) и получать результат просто доставая значение из оной!

[Kostia]

А можно по подробнее для соотношения:

f(n!) =f ( f(8**m) * f(k!) )

[evg_m]

f(n!) 
=f(1*2*...*n) 
=f(f(1)*f(2)*...*f(10)*f(11)*...*f(n)) 
=f(f(1)*f(2)*...*f(10)*f(11)*...*f(r*10)*f(r*10+1)*...*f(r*10+k))
=f(f(1)*f(2)*...*f(1) *f(1) *...*f(r)   *f(1)     *...*f(k)) 
=f(f(1)**m * f(2)**m * ... *f(9)**m * f(1)*...f(k) 
=f(f(1*2*...*9)**m * f(1)*...f(k) ) 
=f(f((1*2*...*9)**m) * f(k!) ) 
=f(f(      f(8)**m)  * f(k!) 
=f(8**m) *f(k!)

[Plague]

проходит все 20 тестов:

var n,i:longint;
begin
  read(n);
  f:=1;
  for i:=2 to n do
  begin
    f:=f*i;
    while f mod 10=0 do f:=f div 10;
    f:=f mod 100000
  end;
  write(f mod 10)
end.