1. 题目

传送门=￣ω￣=

题意：给出 $n$ ，求 $n!$ 的最右边一个非零位的值

2. 题解

对于这题确实是可以用 $O(n)$ 或 $O(nlogn)$ 级别的算法做

但是我们怎么能止步于如此浅薄的层次呢 QvQ

参见 OEIS – A008904

算法过程：

读入 $A$
将 $A$ 转换为 $5$ 进制，得到 $5$ 进制数字 $A_5$ ，其第 $i$ 位的值为 $A_5[i]$ （ $i$ 从 $0$ 开始）
设 $t$ 为 $\sum_{i \text{ mod } 2 =0} A_5[i]$
设 $x$ 为 $\sum A[i] * i$
设 $z$ 为 $x+\frac{t}{2}\text{ mod }4$
设 $y$ 为 $2^z$
则答案为 $\{6 * (y\text{ mod }2)+y * [1-(y\text{ mod }2)]\} \text{ mod }10$

复杂度 $O(log_5A)$

代码：

#include <bits/stdc++.h>

using namespace std;

int a, x, t, z, y;

vector<int> a5;

void ito5() {while (a) a5.push_back(a % 5), a /= 5;}

int main(int argc, char const* argv[])
{
    scanf("%d", &a), ito5();
    for (int i = 0; i < a5.size(); i += 1)
    {
        if (!(a5[i] & 1)) t += a5[i];
        x += a5[i] * i;
    }
    z = (x + (t >> 1)) % 4, y = (1 << z);
    printf("%d\n", (6 * (y & 1) + y * (1 - (y & 1))) % 10);
    return 0;
}