TOJ 1226: Last non-zero Digit in N! 求N！第一个不为0的尾数

女爷i 2022-05-06 10:56 94阅读 0赞

## **1226: Last non-zero Digit in N!** ##

**时间限制(普通/Java):1000MS/10000MS 内存限制:65536KByte  
总提交: 301 测试通过:102**

**描述**

The expression N!, read as "N factorial," denotes the product of the first N positive integers, where N is nonnegative and no more than 200 digits. 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 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!.

**输出**

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

**样例输入**

1  
2  
26  
125  
3125  
9999

**样例输出**

1  
2  
4  
8  
2  
8

**题目来源**

[South Central USA 1997][]

这道题我用Java打表到120肉眼看规律看了半个小时没看出来...

看了题解才发现，还是要考虑5，是我太年轻了...

处理阶乘的时候考虑5的个数，然后相应的除以2的个数，可以得到循环结。

//TOJ 1226
    #include <iostream>
    #include <queue>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <ctime>
    #include <vector>
    #include <cmath>
    #include <cstdlib>
    using namespace std;
    //打标循环结的时候要把5都去掉 
    const int maxn=1e3+10;
    int f[20]={1,1,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2};
    char a[maxn];
    int c[maxn];
    int main()
    {
        while(scanf("%s",a)!=EOF)
        {
            int i,j,k,n,ans=1,t;
            n=strlen(a);
            for(i=0;i<n;i++)
                c[n-1-i]=a[i]-'0';
            while(n>1)
            {
                while(c[n-1]==0)n--;
                ans=ans*f[c[1]%2*10+c[0]]%10;
                t=0;
                for(i=n-1;i>=0;i--)
                {
                    t=t*10+c[i];
                    c[i]=t/5;
                    t=t%5;
                }
            }
            printf("%d\n",ans*f[c[0]]%10);
        }
        return 0;
    }

[South Central USA 1997]: http://210.32.82.1/acmhome/search.do?method=simpleSearch&searchFrom=Source&queryString=South+Central+USA+1997