Last non-zero Digit in N!

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5454 Accepted Submission(s): 1348

Problem Description

The expression N!, read as "N factorial," denotes the product of the first N positive integers, where N is nonnegative. So, for example,
N N!
0 1
1 1
2 2
3 6
4 24
5 120
10 3628800

For this problem, you are to write a program that can compute the last non-zero digit of the factorial for N. For example, if your program is asked to compute the last nonzero digit of 5!, your program should produce "2" because 5! = 120, and 2 is the last nonzero digit of 120.

Input

Input to the program is a series of nonnegative integers, each on its own line with no other letters, digits or spaces. For each integer N, you should read the value and compute the last nonzero digit of N!.

Output

For each integer input, the program should print exactly one line of output containing the single last non-zero digit of N!.

Sample Input

1 2 26 125 3125 9999

Sample Output

1 2 4 8 2 8

Source

South Central USA 1997

Recommend

JGShining

#pragma comment(linker, "/STACK:102400000,102400000") 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <map>
#include <queue>
#include <sstream>
#include <iostream>
using namespace std;
#define INF 0x3fffffff


int n;
int save[10]={1,1,2,6,4,2,2,4,2,8};
char s[1100];
int d[1100];
int i,ti;
int tmp1;
int cnt;

int dfs(int len)
{
    int tmp=1;
    for(i=len;i>=0;i--)
        if(d[i]!=0) break;
    if(i<0)
    {
        return 1;
    }
    if(i==0)
    {
        return save[d[0]];
    }
    if(d[1]%2==0) tmp=6;
    else tmp=4;

    tmp = ( tmp*save[d[0]] )%10;

    ti=i;
    for(;i>=0;i--)
    {
        tmp1=d[i]%5;
        d[i]/=5;
        if(i!=0)
            d[i-1]+=tmp1*10; //将余数向下推
    }
    
    return (tmp*dfs(ti))%10;
}

int main()
{
    //freopen("C:\Users\Administrator\Desktop\in.txt","r",stdin);
    //freopen("C:\Users\Administrator\Desktop\in.txt","w",stdout);
    while(~scanf("%s",s))
    {
        //主要是将所有数2和5因子提取出来就可以了,剩下来的取最后一个数即可
        //然后就是最后一位怎么看了,
        int len=strlen(s);
        memset(d,0,sizeof(d));
        cnt=0;
        for(int i=0;i<len;i++)
            d[len-1-i]=s[i]-'0';
        printf("%d
",dfs(len-1));
    }
    return 0;
}

2015.11.20.。。

又走到这步。今天看数论的是看不小心瞄到了这题，心想多年前都能做出来，现在怎么没什么想法了。

然后推了半天，自己想出一个解法。

我们可以发现，每乘5个数（1-5，或6-10），相当于乘2.（然后再往5^2 ,5^3...推）

然后就很好做了，把n装化为5进制，然后一下就可以出结果了。

留个代码纪念下。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;

char str[10100];
int num[10100];
int ans[10100];

int chg(char c)
{
    return c-'0';
}


int main()
{
    while( scanf("%s",str) != EOF )
    {
        int len=strlen(str);
        for(int i=0;i<len;i++)
            num[i] = chg( str[i] );
        int cnt=0;
        for(int i=0;i<len;i++)
            if(num[i]==0) cnt++;
            else break;
        int wei=0;
        int from=10,to=5;
        while( cnt < len )
        {
            //然后做一次除法
            for(int i=cnt;i<len;i++)
            {
                num[ i+1 ] += (num[i]%to)*from;
                num[ i ] /= to;
            }
            ans[ wei++ ] = num[len]/from;
            num[len]=0;
            for(int i=cnt;i<len;i++)
            {
                if(num[i]==0) cnt++;
                else break;
            }
        }
        /*
        for(int i=wei-1;i>=0;i--)
        {
            printf("%d",ans[i]);
        }
        printf("
");
        */
        int tmp = 1;
        int sum = 1;
        for(int i=0;i<wei;i++)
        {
            int some=ans[i+1]%2==0?0:5;
            for(int j=1+some;j<=ans[i]+some;j++)
            {
                sum = (sum*j*tmp);
                sum = sum%10;
            }
            tmp = tmp*2;
            tmp = tmp%10;
        }
        printf("%d
",sum);
    }
    return 0;
}