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;
}