洛谷P1134 阶乘问题

题目描述

也许你早就知道阶乘的含义，N阶乘是由1到N相乘而产生，如：

12! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x 11 x 12 = 479,001,600

12的阶乘最右边的非零位为6。

写一个程序，计算N(1<=N<=50,000,000)阶乘的最右边的非零位的值。

注意:10,000,000！有2499999个零。

输入输出格式

输入格式：

仅一行包含一个正整数N。

输出格式：

单独一行包含一个整数表示最右边的非零位的值。

输入输出样例

输入样例#1：

输出样例#1：

一般的做法是约分乘数，统计约掉2和5的次数，相互抵消，最后计算多出来的2……

隔壁rlt这样做跑了1000ms

然而我暴力乘居然跑了700+ms

迷……

 1 /*by SilverN*/
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<cmath>
 7 using namespace std;
 8 long long n;
 9 long long tmp;
10 int main(){
11     long long i;
12     scanf("%d",&n);
13     tmp=1;
14     for(i=1;i<=n;i++){
15         tmp=tmp*i;
16         while(tmp%10==0) tmp/=10;
17         tmp%=10000000LL;//迷，%100的话会错 
18     }
19     printf("%lld
",tmp%10);
20     return 0;
21 }

暴力

又写了个高端一点的解法，500+ms

 1 /*by SilverN*/
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<cmath>
 7 #include<vector>
 8 using namespace std;
 9 int x[10][10];
10 int n;
11 int cnt=0;
12 int main(){
13     int i,j;
14     for(i=1;i<=9;i++)
15      for(j=1;j<=9;j++)
16        x[i][j]=(i*j)%10;
17     scanf("%d",&n);
18     int tmp=n;
19     while(tmp){cnt+=tmp/5;tmp/=5;}
20     int ans=1;
21     for(i=1;i<=n;i++){
22         tmp=i;
23         while(tmp%5==0)tmp/=5;
24         while((tmp&1)==0 && cnt){
25             --cnt;
26             tmp/=2;
27         }
28         ans=x[ans][tmp%10];
29     }
30     printf("%d
",ans);
31     return 0;
32 }