题解 P1134 【阶乘问题】

· · 题解

{上次提交匆忙，没有写清楚，抱歉了。。}

拿到这题，首先，我就决定模拟，取最后一个非零为来做阶乘。于是呢，样例过了；自己编的个数据，没过。

于是乎，我没事找事编了个高精阶乘（不附代码了，写得很渣），经过一番辛苦调试，找到在25！的时候会出错。。。

然后我就请出了神器——计算器，帮我查错，得到：6*25=150—>5；36*25=900—>9；936*25=23400—>4；3936*25=98400—>4；

我想，既然，25*936时不会出错，那应该在*25时mod1000就行了。

但，超时，超时！！

作为一个只刷了不到两年题的菜鸟，我没有想到大佬们的做法，于是，我决定：

打表！

既然数据大时会超时，那我就分段，打表！

附上代码（及更多说明）：

···program kjsdlf;

var i,j:longint;m,n,ans:int64;
function check(x:int64):int64;{这个函数来完成计算每次mod的值。}
var i,j,k:longint;
begin
i:=0;
while x>0 do begin inc(i);x:=x div 10;end;
check:=1;
for j:=1 to i do check:=check*10;
end;
procedure jiecheng(o,p,x:int64);{本来不用写过程的，但为了使打表打得更清晰，写一个过程。}
var i:longint;
begin
for i:=o to x do         {就是这个for循环进行主要的答案计算工作，求阶乘。}
begin
p:=p*i;
while p mod 10=0 do p:=p div 10;
p:=p mod check(i);
end;
ans:=p;
end;
begin
read(n);
if n<=5000000 then jiecheng(2,1,n);                                                                        {呀呀呀，打表部分，for循环太多会超时。。}
if (n>5000000)and(n<=10000000) then jiecheng(5000001,2899904,n);                 {于是，最好的方法就是。。分段求解。}
if (n>10000000)and(n<=15000000) then jiecheng(10000001,6993408,n);             {我们先计算出jiecheng(5000000)的最后几位}
if (n>15000000)and(n<=20000000) then jiecheng(15000001,30936576,n);           {然后从jiecheng(5000001)开始计算。}
if (n>20000000)and(n<=25000000) then jiecheng(20000001,92463616,n);           {以此类推。。。}
if (n>25000000)and(n<=30000000) then jiecheng(25000001,2899904,n);
if (n>30000000)and(n<=35000000) then jiecheng(30000001,22198016,n);
if (n>35000000)and(n<=40000000) then jiecheng(35000001,69239296,n);
if (n>40000000)and(n<=45000000) then jiecheng(40000001,5589504,n);
if (n>45000000) then jiecheng(45000001,33662336,n);
writeln(ans mod 10);                                      {在打表的时候，只写jiecheng(2,1,n)，然后不加mod 10输出答案（用来？打表！）}
end.···