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;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

2 条评论

litble · 2018年4月4日 11:12 上午

太强啦

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注