题解 | #阶乘末尾非零数字#

题意：求 末尾非零数

题解参考了前排大佬 丨阿伟丨 的代码

题意即求

注意到，任何一个偶数 乘 6 所得数的个位不变，为什么呢？我们考虑中国剩余定理

根据

那么

对于 的情况， 必然为偶数，因此 ，因此求一个偶数 模 10，即求

那么本题就可以这么做

注意 ，因此我们仅需考虑 的个位

我们有一种接近常数 求 的方法

具体地： 先预处理出 0~9 的阶乘去除含5的因子 的 末尾非零数字

int a[10] = {1, 1, 2, 6, 4, 4, 4, 8, 4, 6};

注意，当且仅当 的末尾非零数字是 1，对于 的情况，个位为 1 时的末尾非零数字是 6，然后再乘基础的 得出 的解。

我们可以类比勒让德定理，在 的常数时间内求解

我们知道

因此，若 ，那么有（此处也可取等号，因为 10 与答案无关， 和 个位都是 2）

然而 中， 里可能有非 5 的因子，我们需要乘回来，设答案为 ，那么

时，

那么答案即为

其中 3 模 5 的阶为 4，即

AC 代码

#include <iostream>
using namespace std;

int a[10] = {1, 1, 2, 6, 4, 4, 4, 8, 4, 6};
int p3m5[4] = {1, 3, 4, 2};
int f(int n) {
    if (n == 0) return 1;
    int ans = n > 10 ? 6 : 1; // 此处也可取等号，因为 10 与答案无关，（6*2 和 1*2 个位都是 2）
    (ans *= a[n%10]) %= 10;
    return ans * f(n/5) % 10;
}

int main() {
    int n; cin >> n;
    if (n < 2) return cout << "1\n", 0;
    int res = f(n) % 5;

    int c5 = 0;
    int t = n;
    while (t) { t /= 5; c5 += t; }
    (res *= p3m5[c5 % 4]) %= 5;
    (res *= 6) %= 10;
    cout << res << '\n';
}