题目链接

阶乘末尾非零数字

题目描述

给定一个正整数 ，记其阶乘为：。

请你输出 的十进制表示中，从右往左数第一个非零数字的数值。

输入:

  • 一行一个整数 ()

输出:

  • 一个整数，代表 末尾第一个非零数字

解题思路

这道题要求我们计算 的最后一个非零数字。当 很大时，直接计算 会溢出，因此必须使用数论方法。

末尾的零是由因子 产生的。 的质因数分解中， 的幂次 总是大于等于 的幂次 。最后一个非零数字，就是将 中所有的因子 (即 对 ) 除掉后，结果对 取模。

直接在模 意义下除以 是不行的，因为 和 不互质。但我们可以利用中国剩余定理的思想来解决。 一个数模 的值由它模 和模 的值唯一确定。

  1. 求解模 :

    在模 意义下， 的乘法逆元是 。所以 。

    我们令 。可以推导出递归式：，其中 是 到 中所有不含因子 的数的乘积模 。 可以通过预计算一个周期表快速求出。

  2. 求解模 : 对于 ，，所以 (其中 是奇数) 是一个偶数。因此 。对于 ，答案是 。

  3. 合并结果: 对于 ，我们已经知道 是一个偶数 。同时我们计算出了它模 的值 。这两个条件可以唯一确定最终答案。例如，如果 ，那么在偶数中只有 满足 。

综上，算法步骤如下：

  1. 处理 的边界情况，答案为 。
  2. 计算 中因子 的数量 。
  3. 递归计算 。
  4. 计算 。
  5. 找到唯一的偶数，使得它模 等于 ，输出结果。

代码

#include <iostream>

using namespace std;
using LL = long long;

const int table[10] = {1, 1, 2, 6, 4, 4, 4, 8, 4, 6};
const int pow3_mod5[4] = {1, 3, 4, 2};

LL H(LL n) {
    if (n == 0) {
        return 1;
    }
    LL P_n = (n / 10 > 0) ? 6 : 1;
    P_n = (P_n * table[n % 10]) % 10;
    return (P_n * H(n / 5)) % 10;
}

int main() {
    LL N;
    cin >> N;

    if (N < 2) {
        cout << 1 << endl;
        return 0;
    }

    LL C5 = 0;
    LL temp = N;
    while (temp > 0) {
        temp /= 5;
        C5 += temp;
    }

    LL H_N = H(N);
    LL H_N_mod5 = H_N % 5;
    LL pow3 = pow3_mod5[C5 % 4];
    LL Z = (H_N_mod5 * pow3) % 5;

    int result;
    if (Z == 0) result = 0;
    else if (Z == 1) result = 6;
    else if (Z == 2) result = 2;
    else if (Z == 3) result = 8;
    else result = 4;

    cout << result << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    static int[] table = {1, 1, 2, 6, 4, 4, 4, 8, 4, 6};
    static int[] pow3_mod5 = {1, 3, 4, 2};

    public static long H(long n) {
        if (n == 0) {
            return 1;
        }
        long P_n = (n / 10 > 0) ? 6 : 1;
        P_n = (P_n * table[(int)(n % 10)]) % 10;
        return (P_n * H(n / 5)) % 10;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();

        if (N < 2) {
            System.out.println(1);
            return;
        }

        long C5 = 0;
        long temp = N;
        while (temp > 0) {
            temp /= 5;
            C5 += temp;
        }

        long H_N = H(N);
        long H_N_mod5 = H_N % 5;
        long pow3 = pow3_mod5[(int)(C5 % 4)];
        long Z = (H_N_mod5 * pow3) % 5;

        int result;
        if (Z == 0) result = 0;
        else if (Z == 1) result = 6;
        else if (Z == 2) result = 2;
        else if (Z == 3) result = 8;
        else result = 4;

        System.out.println(result);
    }
}

import sys

sys.setrecursionlimit(200000)

table = [1, 1, 2, 6, 4, 4, 4, 8, 4, 6]
pow3_mod5 = [1, 3, 4, 2]
memo_H = {}

def H(n):
    if n in memo_H:
        return memo_H[n]
    if n == 0:
        return 1
    
    P_n = 6 if n // 10 > 0 else 1
    P_n = (P_n * table[n % 10]) % 10
    
    result = (P_n * H(n // 5)) % 10
    memo_H[n] = result
    return result

def main():
    N = int(sys.stdin.readline())

    if N < 2:
        print(1)
        return

    C5 = 0
    temp = N
    while temp > 0:
        temp //= 5
        C5 += temp
        
    H_N = H(N)
    H_N_mod5 = H_N % 5
    pow3 = pow3_mod5[C5 % 4]
    Z = (H_N_mod5 * pow3) % 5
    
    result = 0
    if Z == 1: result = 6
    elif Z == 2: result = 2
    elif Z == 3: result = 8
    elif Z == 4: result = 4
        
    print(result)

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：数论、递归、中国剩余定理。通过递归将问题分解，并结合模运算性质求解。

  • 时间复杂度： - 递归函数 的深度为 ，每次递归的计算是 。

  • 空间复杂度： - 递归调用栈的深度。Python 代码中使用了 memoization，空间复杂度会略高。