阶乘末尾非零数求和
Time Limit:1s Memory Limit:1000k
Total Submit:4730 Accepted:1336
下载样例程序(PE)
下载样例程序(ELF)


--------------------------------------------------------------------------------

Problem
对于小于25000的自然数n,求阶乘n!,(n-1)!,(n-2)!...3!,2!,1!右边的非零数之和。

例如：

当n=5时，
5!=120,右边非零数为2;
4!=24,右边非零数为4;
3!=6,右边非零数为6;
2!=2,右边非零数为2;
1!=1,右边非零数为1。
其右边的非零数之和为15。

Input
本题有多组数据，每组数据包含一个正整数N(N不大于25000)占一行。

Output
对给定的每组输入数据，输出一个整数。每个结果占一行。不要输出额外的空行。

Sample Input
5
10
1

Sample Output
15
39
1

#include<iostream.h>
int deal(int n,int &bn)
/*n为待处理的数，处理的结果是先去除尾部所有0，然后去掉2或5的因子
*bn返回因子2的个数减因子5的个数
*函数返回去掉这些因子的n
*/
{
    while(n%10==0)n/=10;
    if(!(n&1))
        do{n>>=1;++bn;}
        while(!(n&1));
    else
        while(n%5==0){n/=5;--bn;}
    return n;
}
int main()
{
    static int d[4]={6,2,4,8};//d[n]:=2^n%10，2的n次方的个位数,n>0
    int n,bn,j,t;
    long s;
    while(cin>>n)
    {
        for(bn=0,t=1,s=1,j=2;j<=n;++j)
        {
            t=t*deal(j,bn)%10;
            s+=t*d[bn%4]%10;
        }
        cout<<s<<endl;
    }
    return 0;
}

评论