题解 P1134 【阶乘问题】

XZYQvQ · 2018-04-04 09:29:57 · 题解

安利自己的博客QvQ：http://www.k-xzy.xyz/archives/5073

对于这题确实是可以用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)

（貌似楼下也有个复杂度同级的算法，但这个算法不带常数233333～）

代码：

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