题解 P1134 【阶乘问题】

· · 题解

基于这样一个事实：以上几个数 *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）！的 末尾非零位

递归处理 即可

PASCAL代码:

const   
  data:array [0..3] of 0..9=(8,4,2,6);   
var   
  i,ans,a,b,c,n,f:longint;   
begin  
  readln(n);  
  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;   
  write(ans);   
end.