usaco-Section 3.2-Factorials

The factorial of an integer N, written N!, is the product of all the integers from 1 through N inclusive. The factorial quickly becomes very large: 13! is too large to store in a 32-bit integer on most computers, and 70! is too large for most floating-point variables. Your task is to find the rightmost non-zero digit of n!. For example, 5! = 1 * 2 * 3 * 4 * 5 = 120, so the rightmost non-zero digit of 5! is 2. Likewise, 7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040, so the rightmost non-zero digit of 7! is 4.

PROGRAM NAME: fact4

INPUT FORMAT

A single positive integer N no larger than 4,220.

SAMPLE INPUT (file fact4.in)

7

OUTPUT FORMAT

A single line containing but a single digit: the right most non-zero digit of N! .

SAMPLE OUTPUT (file fact4.out)

4

分析，如果是普通的乘起来，无法知道最后一位有效的数字在哪，因此不难发现我们可以把每一个数分解，然后把2的数量减去5的数量，最后全部乘起来，就是所求的有效数字，每一次乘的时候mod10，最后输出答案。
代码如下：

/*
ID: yizeng21
PROB: fact4
LANG: C++
*/
#include<stdio.h>
int time[10000];
void fenjie(int s){
    int t=2;
    while(s!=1){
        if(s%t==0){
            s/=t;
            time[t]++;
        }else t++;
    }
    return;
}
int main(){
    freopen("fact4.in","r",stdin);
    freopen("fact4.out","w",stdout);
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        fenjie(i);
    }
    int ans=1;
    for(int i=3;i<=n;i++){
        if(i==5)continue;
        for(int j=1;j<=time[i];j++){
            ans=ans*i%10;
        }
    }
    for(int i=1;i<=time[2]-time[5];i++){
        ans=ans*2%10;
    }
    printf("%d\n",ans);
}

usaco-Section 3.2-Factorials

原文：http://www.cnblogs.com/buffms/p/5159227.html