题解 P1134 【阶乘问题】

· · 题解

本题用存非零的最后一位的方法是有反例的，

因为当的之前乘积的非零最后一位和当前这个数的非零最后一位相乘，可能乘积 mod 10会等于0。

这时就要用到之前乘积的非零倒数第二位了，可是程序并没有存这个东西。

而且即使存了，那么倒数第2、3、4、5.......位都会有诸如倒数第一位的情况，那就变成是每相乘一次就要存储一次积，但这时就会超过计算机能存储的最大整数。

而且即使用高精度也会超时，[color=red]那么就需要考虑如何使这种情况“分离”出来单独处理。[/color]

-------------------------------以下为题解-------------------------------

既然要“分离”出这种情况，

那么就考虑有哪几个小于10大于0的两个自然数相乘的乘积 mod 10等于0。

不难发现只有2、4、6、8去乘5的乘积才会如此，而2、4、6、8的质因子中又都有2，

由此只要让一个数不能被5和2整除，剩下的没有2和5的因子的两个数再怎么相乘，都不可能让乘积 mod 10等于0了。

好了，那么现在开始考虑怎么处理。

设要运算的数为i（1<=i<=n），先去掉最右边所有的0。

接着设一个变量k，为i！去掉最右边所有的0并分解质因数后得出k个2，

以及一个变量ans，用来存储去掉2的因子的最终结果。

（div为整除的意思）

只要i mod 2=0 ，那么就让i div 2（消掉这个数为2的因子），并在k上加1；

接着只要i mod 5=0 ，那么就让i div 5（消掉这个数为5的因子），并在k上减1。

（大家可以换一个思路来理解，就是k被减掉j个1代表(i-1)！（已去掉最右边所有的0）*i（同样已去掉最右边所有的0）的乘积最右边的0有j个，而题目要求是取最右边非0的数，那么这j个2和5就要“扔掉”，不用在最终结果上乘啦）

最后就在ans乘上处理完的数再 mod 10，这样这个数i就处理完了~

因为2的k（k>0）次方的最右边的非零位只可能是6、2、4、8[color=purple]

【分布规律为k mod 4=0时为6，k mod 4=1时为2，k mod 4=2时为4，k mod 4=3时为8】[/color]，

所以最终输出{k mod 4所对应的值乘上ans，得出的乘积再 mod 10}，结束~！

附上代码：


program ex1134;
const
  a:array[0..3] of longint=(6,2,4,8);
var
  i,j,k,m,n,s,t:longint;
begin
  readln(n);
  s:=1;
  k:=0;
  for i:=2 to n do
  begin
    j:=i;
    while j mod 10=0 do
      j:=j div 10;
    while j mod 5=0 do
    begin
      j:=j div 5;
      k:=k-1;
    end;
    while j mod 2=0 do
    begin
      j:=j div 2;
      k:=k+1;
    end;
    s:=(s*j) mod 10;
  end;
  s:=s*a[k mod 4];    
//k不可能小于0，因为最终结果5的因子在题目所述的前提下一定不会比2的因子多= =
  writeln(s mod 10);
end.