USACO/fact4

水题

直接留下末五位，模拟至多乘5000次。全部0.00 second。 jzoi

分析

  我们用一个数组m来存放1~n个数，然后先把m数组中所有数的5除掉，用time记录除了多少次，再依次把m数组中数的2除time次，然后直接将m数组中所有的数相乘，取每次积的个位即可，核心代码如下。

    time:=0;
    for i:=1 to n do
      while m[i] mod 5=0 do
        begin
          m[i]:=m[i] div 5;
          time:=time+1;
        end;
    for i:=1 to n do
      while (m[i] mod 2=0) and (time>0) do
        begin
          m[i]:=m[i] div 2;
          time:=time-1;
        end;
    ans:=1;
    for i:=1 to n do
      ans:=ans*m[i] mod 10;
    writeln(ans);

简单的把末尾的0去掉是不行的，因为我们不知道现在不是0的位会不会乘上下一个数之后就变成0了。

因为10=2*5,所以每有一个0就有一对2*5=10出现，反之，如果这个数的质因数分解没有成对的2，5，我们就可以简单的对10求模，而不用管前面的数字，因为它一定不会产生0。

所以我们只要在处理阶乘的时候消掉所有成对的2和5就行了，容易理解，N!的质因数分解式里因子2远比5要多，所以只需要记录因子2的个数，有因子5就消掉，最后再把2乘回去就行了。

可以直接用高精度乘法计算，5000位就够了，每位存储一个四位数，打印时处理一下。

甚至可以连高精度都不用，用一个变量j记录i!的最后四位末尾非零数，在计算(i+1)!时只需要计算(i+1)*j即可。

更简洁的方法是，一遍循环消除5并记录5的个数，第二遍循环消除同样个数的2并计算末位。

 关键一：消除5的同时记录个数，然后按照个数消除2.
 关键二：仅记录最后一位即可。

代码见pascal--afterdr1

我晕了，我用了个最笨的方法--直接高精度，每位就储存一个一位数，当位数超过1500位时就把1500位以后的数去掉（我的想法是 阶乘乘出1000多个0好像不太现实），最后从各位往前查找不是0的数。。。然后可怕的事情发生了，我竟然真的ac了，我晕20:55 2009年8月24日 (CST)20:55 2009年8月24日 (CST)20:55 2009年8月24日 (CST)

[最简单的code：见C++代码，关键代码4行。]

我用了个比较猥琐的办法.....只记录最后的非0的5位数....不停地乘就ok....极其简单....不涉及任何高精度之类的知识。 详情见代码。——瀑布飞鹰

我的方法是先计算 n! 中有多少个 5 因子，并记录下来。然后从 1 到 n 把每个因数列出来，如果能去掉 2 和 5 (数量都是因子 5 的个数)，就把 2 和 5 去掉。这样中间计算的数只用保留 1 位(mod 10) 就可以了。详见jiangan2 的代码——Fruderica。 PS:上面的瀑布飞鹰同学 AC 的原因是 4220 包含最大的 5 的幂是 3125 (5^5)，所以取末尾 5 位是足够的。

参考代码

C++
c
pascal

引用

[1]

[2]

可以现将每次的乘数中的2和5提取出来，然后只乘剩下的数的最后一位，记录下2和5的个数，最后消掉少的那个 比如有5个2 3个5 就等价于2个2 0个5然后把2 和5乘回去 一边乘一边MOD 10 即可 详细代码见C++代码