阶乘最后面的非零位

题目描述

给定整数 $N$ （ $1 \le N \le 4220$ ），求 $N!$ 十进制表示中最后一位非零数字（如 $5!=120$ 答案为 2）。

思路

末尾 0 全来自因子 $2\times5$ ，把每个 5 配一个偶数消掉后，按 5 个数一组递推 $D(n)=D(\lfloor n/5\rfloor)\times D(n\bmod 5)\times 2^{\lfloor n/5\rfloor} \bmod 10$ （ $n<5$ 出口为 $1,1,2,6,4$ ）， $O(\log N)$ 求解。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22import sys
from functools import lru_cache


@lru_cache(maxsize=None)
def d(n: int) -> int:
    """n! 去掉所有因子 10（即末尾 0）后的个位数字。

    递推：D(n) = D(n//5) * D(n%5) * 2^(n//5) mod 10。
    - 每 5 个数提出一个因子 5，与偶数配对成一个 10，把因子 5 全部消掉；
    - 消掉这轮 5 的同时，每 5 个数还剩下 2、4、6、8 各一个，
      乘积 2*4*6*8 ≡ 2^4 ≡ 1 (mod 10)，只余下「5 的倍数之外的那个残数」；
    - 商 q = n//5 继续递归（里面还有 5 的倍数），其贡献相当于多乘 2^q。
    """
    if n < 5:
        return (1, 1, 2, 6, 4)[n]
    q, r = divmod(n, 5)
    # (1,2,4,8)[q%4] 即 2^q 的个位（q≥1 时 2^q 个位按 2,4,8,6 循环，q%4=0 时为 6，但此处 q≥1 故 2^0=1 不会误触发）
    return d(q) * (1, 1, 2, 6, 4)[r] * (1, 2, 4, 8)[q % 4] % 10


print(d(int(sys.stdin.read())))

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 10:29
 * update_at: 2026-10-06 10:30
 */
#include <cstdio>

typedef long long ll;

// D 表：D[n] = n! (n < 5) 去掉末尾 0 后的个位，作为递归出口
ll d5[5] = { 1, 1, 2, 6, 4 };

// p2[k % 4] = 2^k 的个位（2 的个位按 2,4,8,6 循环）
ll p2[4] = { 6, 2, 4, 8 };

// d(n) 求 n! 去掉全部末尾 0 后的个位：
// 把每个 5 的倍数提出一个因子 5 与偶数配成 10 消掉，
// 剩余部分是 (n/5)! 继续递归，同时补上被配对消耗的偶数，即乘 2^(n/5) 的个位。
ll d(ll n) {
    if (n < 5) return d5[n];
    ll q = n / 5, r = n % 5;
    return d(q) * d5[r] % 10 * p2[q % 4] % 10;
}

int main() {
    ll n;
    scanf("%lld", &n);
    printf("%lld\n", d(n));
    return 0;
}

阶乘最后面的非零位

目录

题目描述

思路

参考代码