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 上午

太强啦

发表评论

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

你是机器人吗? =。= *