Factorials 3.2

求阶乘的最后一位非零整数。开始天真无鞋,以为只取最后非零位累成即可.然后自然出错

官方解释,可能存在xx12*xxx5,如果只取最后非零位累乘...2*5=10 mode 10 ==1 ,这样两个数十位上的就被忽略了...

大概是这个意思。然后解题思路是,10全部是由2*5产生的,即使是10本身也是2*5,所以只要去掉累乘中的所有2,5对就好了

而2出现的概率远大于5,用数组arry[n]保存1到n,然后每个数mod5 直到因子5全部被剔除 ,同时记录剔除的个数m,

然后再对更新后的arry[n]剔除m个2（记住除多除少了）这样就不会产生10了.

在取最后一位累乘即可. 看似简单,本菜真想不出来了

 1 /*
 2 
 3 ID: hubiao cave
 4 
 5 PROG: fact4
 6 
 7 LANG: C++
 8 
 9 */
10 
11 
12 
13 
14 #include<iostream>
15 
16 #include<fstream>
17 
18 #include<string>
19 
20 using namespace std;
21 
22 
23 
24 int main()
25 
26 {
27 
28     ifstream fin("fact4.in");
29     ofstream fout("fact4.out");
30 
31     int m[4300];
32     int n,time=0;
33     int ans=1;
34     fin>>n;
35 
36     for(int i=1;i<=n;i++)
37     {
38         m[i]=i;
39         while(m[i]%5==0)
40         {
41             time++;
42             m[i]/=5;
43         }
44     }
45     
46     for(int i=1;i<=n;i++)
47     {
48         while(m[i]%2==0&&time>0)
49         {
50             m[i]/=2;
51             time--;
52         }
53     }
54 
55     for(int i=1;i<=n;i++)
56         ans=ans*m[i]%10;
57     fout<<ans<<endl;
58     return 0;
59 
60 
61 }