求n的阶乘最后一位非0数字的问题。请人分析pascal代码

Question

题目：
第2题 阶乘问题（fact.pas/in/out）

也许你早就知道阶乘的含义，N阶乘是由1到N相乘而产生，如：
12! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x 11 x 12 = 479,001,600
12的阶乘最右边的非零位为6。
写一个程序，计算N(1<=N<=50,000,000)阶乘的最右边的非零位的值。
注意:10,000,000！有2499999个零。

输入
仅一行包含一个正整数N。

输出
单独一行包含一个整数表示最右边的非零位的值。

样例
fact.in
12

fact.out
6

分析代码
第1个
program fact;
const
data:array [0..3] of 0..9=(8,4,2,6);
var
i,ans,a,b,c,n,f:longint;
procedure init;
begin
assign(input,'fact.in');reset(input);
assign(output,'fact.out');rewrite(output);
readln(n);
end;

procedure doit;
begin
b:=1; a:=n div 10; b:=a mod 4;
if a<=100 then b:=data[b-1];
if a>=1000000 then b:=data[b-2];
if (a>100) and (a<1000000) then b:=data[b];
c:=n mod 10; f:=1;
for i:=1 to c do f:=f*i;
f:=f*b;
while f mod 10=0 do f:=f div 10;
ans:=f mod 10;
end;

procedure terminate;
begin
write(ans);
close(input);close(output);
end;
begin
init;
doit;
terminate;
end.

第2个
program fact;
const
er:array[0..3] of longint=(6,2,4,8);
var
i,j,k,n:longint;
ans:longint;
begin
assign(input,'fact.in'); reset(input);
assign(output,'fact.out'); rewrite(output);

read(n); k:=0; ans:=1;

for i:=1 to n do
begin
j:=i;
while j mod 10=0 do
j:=j div 10;
while j mod 2=0 do
begin
inc(k);
j:=j div 2;
end;
while j mod 5=0 do
begin
dec(k);
j:=j div 5;
end;
ans:=(ans*j) mod 10;
end;
if k>0 then ans:=(ans*er[k mod 4]) mod 10;
writeln(ans);

close(output);
end.

第3个
program fact;
var
n,i,j,count,x,now:longint;
procedure reading;
begin
assign(input,'fact.in');reset(input);
assign(output,'fact.out');rewrite(output);
readln(n);
end;
procedure doit;
begin
count:=0;
x:=1;
for i:=1 to n do
begin
now:=i;
while now mod 2=0 do begin inc(count);now:=now div 2;end;
while now mod 5=0 do begin dec(count);now:=now div 5;end;
if (x*now mod 10=0)then x:=(x*now)div 10 else x:=(x*now)mod 10;
end;
end;
procedure after;
begin
if count>0 then
begin
if count mod 4=0 then x:=(x*6)mod 10;
if count mod 4=1 then x:=(x*2)mod 10;
if count mod 4=2 then x:=(x*4)mod 10;
if count mod 4=3 then x:=(x*8)mod 10;
end;
end;
begin
reading;
doit;
after;
writeln(x);
close(input);close(output);
end.

Answer 1

算法：首先 答案 一定是 2，4，6，8
基于这样一个事实：以上几个数 *6 末尾不变
那么，ans（k*10）=ans（k*6）=ans（k*16）
即： ans（k*2*5）=ans（k*2*8）
于是 将 n！ 中 所有 的 因子 5 全部换成 8 结果是不变的
分类计算： 末尾为1，2，3，4，6，7，8，9 的 直接计算
5，0 把 一个 5 提取出来 ，全部换成8 直接计算得到
提取后 得到一个 子问题 ： （N DIV 5）！的 末尾非零位
递归处理 即可

时间复杂度 O(LOG N）

Answer 2

var
i,j,n:integer;
x,y:string;
function chengfa(a,b:string):string;
var
i,j,h:integer;
x:array[0..254] of integer;
c:string;
begin
fillchar(x,sizeof(x),0);
for i:=1 to length(a) do
begin
h:=ord(a[i])-48;
for j:=1 to length(b) do
x[i+j-1]:=x[i+j-1]+h*(ord(b[j])-48);
end;
c:='';
for i:=length(a)+length(b)-1 downto 1 do
begin
x[i-1]:=x[i-1]+x[i] div 10;
c:=chr(x[i] mod 10+48)+c;
end;
if x[0]>0 then
c:=chr(x[0] mod 10 +48)+c;
while true do
begin
if c[length(c)]='0' then
delete(c,length(c),1)
else
break;
end;
chengfa:=c;
end;
begin
readln(n);
x:='1';
for i:=1 to n do
begin
str(i,y);
x:=chengfa(x,y);
end;
writeln(x);
end.

Answer 3

用高精，然后：
jishuqi:=0;
for i:=阶乘位数 downto 1 do
if 阶乘所得值最后一位是零, then inc(计数器) else write(计数器）；
end.