1066 Last non-zero Digit in N!

• 题目做不出 看答案：参考文献
• https://www.xuebuyuan.com/1394116.html
• https://blog.csdn.net/orangesix/article/details/44190501 (在下面的8/2还是什么只要因子2的数量还有 都不会尾数绝对不会是奇数)
• http://blog.sina.com.cn/s/blog_59e67e2c0100a7yx.html （里面讲了两种解法 第一种也是对一下第一种代码进行修改 ~但超时了）
• https://blog.csdn.net/a601025382s/article/details/38174939
• 一开始想的是一直保留最后一位 只要是0 就把他去掉 这个代码一开始答案正确就没有去多想 然后提交失败后想了很久，发现我们只关心最后一位 却忘了前一位也是跟前一位的值有关系的 这样就导致了误解 一些需要两位数起作用 我们一直保留最后一位这个方法是错误的，一个数相乘答案跟其他位置都有密切联系。
• 例如 我们把98*5 答案是490 尾数正确是9 ，但是我们取尾数相乘的话 仅仅才4 这就是问题所在。

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            long n = sc.nextLong();
            long count = 1;
            for (int i = 1; i <= n; i++) {
                count *= i;
                while (count % 10 == 0) 
                    count /= 10;
                    count %= 10;
            }
                System.out.println(count);
        }
    }
}

所以要改用其他方法
https://baike.baidu.com/item/阶乘/4437932?fromtitle=n%21&fromid=7806135
看了一整天 还是看不懂 突然睡着睡着想到了

//
//  main.c
//  HDOJ1066
//
//  Created by Egger on 18/1/15.
//  Copyright (c) 2015年 Egger. All rights reserved.
//

#include 
#include 
#define SIZE 10
#define MAXH 1000

char Str[MAXH];
int Num[MAXH];

const int FirstTen[SIZE] = {1,1,2,6,4,2,2,4,2,8};
const int Table[SIZE] = {6,6,2,6,4,4,4,8,4,6};
const int DivisionCircle[4] = {2,6,8,4};

int H(int X, int Y)//y小于100  跟百位没有多大关系
{

    int i;

    for(i = 0; i < 4; i++)
    {
        if (X == DivisionCircle[i])
        {
            break;
        }
    }

    return DivisionCircle[(i+Y)%4];
}

int F(char* s)
{
    int i,k;
    int Bit,Carry,Len,Result;

    Len = (int)strlen(s);
    Result = 1;

    if(Len < 2)
    {
        return FirstTen[s[0]-'0'];
    }

    for(i = Len - 1; i >= 0; i--)
    {
        Num[Len-1-i] = s[i] - '0';
    }
    while(Len > 1)
    {
        k = Num[0];
        Carry = 0;
        Num[Len] = 0;
        for(i = 0; i <= Len; i++)
        {
            Bit = Num[i] * 2 +Carry;//因为要把它传到（n/5！相当于*2/10）
            Num[i] = Bit % 10;//适用于所有的数 别管被截掉的尾位
            Carry = Bit / 10;
        }
        for(i = 1; i <= Len; i++)
        {
            Num[i-1] = Num[i];
        }
        if(Num[Len] == 0)
            Len --;

        Result = Result * H(Table[k], Num[0]+Num[1]*10) % 10;//因为每四位一个循环 所以跟百位以上没多大联系
    }

    Result = Result * FirstTen[Num[0]] % 10;

    return Result;
}

int main(int argc, const char* argv[])
{

    while(scanf("%s",Str) != EOF)
    {
        printf("%d\n",F(Str));
    }
    return 0;
}

~~整理很久的思路 终于想清楚了 ~ 改写成java 有不懂可以留言

import java.util.*;

public class Main {
    static int num = 1000;//因为输入值位1000位的数 所以采用数组一个位一个位保存
    static int FirstTen[] = { 1, 1, 2, 6, 4, 2, 2, 4, 2, 8 };//结合上面的代码 一个一个写
    static int DivisionCircle[] = { 2, 6, 8, 4 };
    static int Table[] = { 6, 6, 2, 6, 4, 4, 4, 8, 4, 6 };

    public static int H(int X, int Y) {
        int i;
        for (i = 0; i < 4; i++) {
            if (X == DivisionCircle[i]) {
                break;
            }
        }
        return DivisionCircle[(i + Y) % 4];//因为除数是循环 先找出i的位置 在向右移动Y位，每四位循环一次 所以%4
    }

    public static int funcation(int arr[], int len) {
        int res = 1;
        int k;
        int carry;
        int bit;
        while (len > 1) {
            k = arr[0];
            carry = 0;
            arr[len] = 0;
            for (int i = 0; i <= len; i++) {
                bit = arr[i]*2 + carry;
                carry = bit / 10;
                arr[i] = bit % 10;
            }
            for (int i = 1; i <= len; i++) {
                arr[i - 1] = arr[i]; //可能有些人会想 arr[i-1]不为零 移位覆盖了 不影响吗 真的不影响 因为我们只要求  n/5  按照另外一篇推文里面介绍的递推公式（符合） 包括16/5 = 3 我们只要知道要除有几个2就好
            }
            if (arr[len] == 0) {//持续记录剩下的数的长度
                len--;
            }
            res = res * H(Table[k],arr[0]+arr[1]*10)%10;//结合另外一篇递推公式
        }
        return res * FirstTen[arr[0]] % 10;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String n = sc.next();
            if (n.length() < 2)
                System.out.println(FirstTen[n.charAt(0) - '0']);
            else {
                int arr[] = new int[n.length() + 1];
                for (int i = 0; i < n.length(); i++) {
                    arr[i] = n.charAt(n.length() - 1 - i) - '0';//逆序方便处理
                }
                System.out.println(funcation(arr, n.length()));
            }
        }
    }
}