最近的阶乘问题接触的比较多。
计算n！的末尾非0数是一个比较经典的问题。
那么对于小数据的该问题，还是比较容易的。
RQNOJ点击打开链接SWOJ点击打开链
小数据的方法都是可以过的。
所谓小数据的方法就是，在计算阶乘的时候，末尾0丢掉，高位无用丢掉。这样是不影响最后结果的。
看代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define LL long long
int main(){
int n;
while(~scanf("%d",&n)){
LL ans=1;
for(LL i=1;i<=n;i++){
ans=ans*i;
while(ans%10==0) ans/=10;
if(ans>1000000) ans=ans%1000000;
}
printf("%lld\n",ans%10);
}
return 0;
}
但是，对于大数据的题目，肯定会超时的。所以，我们来学习一下大数据的处理算法。
对于标准类型可存的数据范围来说，有一种更加快速的方法来求解。
分析：
我们知道，在阶乘的过程中，能够得到末尾为0的，就是因子2*5了。
那么在求解n！的末尾非0的时候，我们可以先跳过5的倍数的数。然后，再计算5的倍数的数的末尾非0数。
设G(n)=跳过5的倍数的时候，n！的末尾非0数。
比如：
G(0)=1，G(1)=1，G(2)=2，G(3)=6，G(4)=4，G(5)=4，G(6)=4，G(7)=8，G(8)=4，G(9)=6，G(10)=6，G(11)=6， G(12)=2，G(13)=6，G(14)=4.....
可以发现，除去0，1，其他是以10为一循环的。
那么我们就看轻松的知道，G(n)。
那么接下来的问题就是求5倍数的那些数的末尾非0的。先把5提出来得到：
5(1*2*3*4*5.........)
可以看到，把5提出来以后，就又是一个阶乘序列。
那么，现在的问题就是，怎么样把5给消去。我们知道，消去一个5需要做的就是将一个2与之配对。
原数就要乘以3个2(或者是除以一个2)来弥补。这里为什么？希望，多思考。
这样的话，我们就可以进行，递归求解了。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define LL __int64
const int GN[15]={6,6,2,6,4,4,4,8,4,6};
const int GT[5]={6,2,4,8};
const int G[6]={0,1,2,6,4};
LL f(LL n){
if(n<5) return G[n];
return GN[n%10]*GT[n/5*3%4]%10*f(n/5);
}
int main(){
LL n;
while(~scanf("%I64d",&n)){
printf("%I64d\n",f(n)%10);
}
return 0;
}
即使，这种方法就相当的快速的。但是，对于，标准类型以外的数，是不可以的。
那么，怎么求解字符串才能存储的数据呢？
一下为转载部分。
考虑某一个N!(N>=10)，我们先将所有5的倍数提出来，用1代替原来5的倍数的位置。
由于5的倍数全被提走了，所以这样就不会出现尾数0了。
我们观察一下剩下的数的乘积的尾数，
通过table表，我们发现这10个数的乘积的尾数是6，6*6的尾数还是6，
因此我们将剩下的数每10个分成一组，则剩下的数的乘积的尾数只与最后一组的情况有关，
即与N的最后一位数字有关。
(因为根据最后一位就能知道它在尾数表中处于第几个位置，
只要将尾数表之前的数相乘就得到最后一组的尾数。）
由于我们把5的倍数提出来了，N!中一次可以提出[N/5]个5的倍数，有多少个5，
就需要有多少个2与之配成10，所以有多少个5，最后就要除以多少个2。
注意到除2的结果变化是4个一循环，因此如果有A个5，只需要除(A MOD 4)次2就可以了。
A MOD 4只与A的最后两位数有关，很好求算。
剩下的5的倍数，由于5已经全部处理掉了，就变成[N/5]!。于是，我们可以得到
一个递归关系：
F([N/5]) * table[N的尾数] * 6
F(N) = ----------------------------------- (N > 10)
2^([N/5] MOD 4)
这样我们就得到了一个O(log5(N))的算法，整除5可以用高精度加法做，乘2再除10即可。
整个算法相当巧妙，写起来也比较轻松。
自己修改的代码：好高端。。
Hdu 1066
点击打开链接
#include <cstdio>
#include <cstring>
using namespace std;
const int N=10004;
const int mod[20]={1,1,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2};
int f(char *str){
int len=strlen(str),a[N],i,c,ans=1;
if(len==1) return mod[str[0]-'0'];
for(i=0;i<len;i++){//转化为数字进行处理.
a[i]=str[len-1-i]-'0';
}
//code is amazing!!
for(;len;len=len-(!a[len-1])){
ans=ans*mod[a[1]%2*10+a[0]]%5;
for(c=0,i=len-1;i>=0;i--){//f(n)=f(n/5);
c=c*10+a[i];
a[i]=c/5;
c=c%5;
}
}
return ans+ans%2*5;
}
int main()
{
char str[N];
while(~scanf("%s",str)){
printf("%d\n",f(str));
}
return 0;
}
那么，所有数据范围内的n！末尾非0就总结到这里了。