题解 SP2124【FCTRL4】

· · 题解

SP2124 FCTRL4 - Last Non-Zero Digit of Factorials

建议蓝。

题意

求 f(n)=n! 中最后一位非 0 数，1\le n\le 10^{100}。

思路

显然不能暴力。

引入符号 s(n)=1\times 2\times 3\times 4\times 6\times ...\times 9\times 11 即 n! 中不包含因数 5 的项的乘积。

设 a(n) 表示 s(n) 中最后一位，显然，a(n)\ne 0。

对于 n=1,2,3,...，我们发现 a(n)=1,2,6,4,4,4,8,4,6,6,6,2,6,4,4,4,8,4,6,6,6,...，发现没有？循环节 2,6,4,4,4,8,4,6,6,6。

我们可以先处理出 n\le 10 的 f(n)，然后讨论一下。

n!=s(n)\times 5^{\left\lfloor\frac{n}{5}\right\rfloor}\times (\left\lfloor\frac{n}{5}\right\rfloor)! =\frac{s(n)}{2^{\left\lfloor\frac{n}{5}\right\rfloor}}\times {10}^{\left\lfloor\frac{n}{5}\right\rfloor}\times (\left\lfloor\frac{n}{5}\right\rfloor)!

即 f(n)=\frac{s(n)}{2^{\left\lfloor\frac{n}{5}\right\rfloor}}\times (\left\lfloor\frac{n}{5}\right\rfloor)! 的最后一位非 0 数。

又十分显然 f(n)=\frac{s(n)}{2^{\left\lfloor\frac{n}{5}\right\rfloor}}\times f(\left\lfloor\frac{n}{5}\right\rfloor) 的最后一位非 0 数。

考虑 a(n) 与 a(\left\lfloor\frac{n}{2}\right\rfloor) 的关系。

经过找规律，

a(n)=2\iff a(\left\lfloor\frac{n}{2}\right\rfloor)=6 a(n)=6\iff a(\left\lfloor\frac{n}{2}\right\rfloor)=8 a(n)=8\iff a(\left\lfloor\frac{n}{2}\right\rfloor)=4 a(n)=4\iff a(\left\lfloor\frac{n}{2}\right\rfloor)=2

循环。

又 a(n) 循环，容易计算，所以 \frac{s(n)}{2^{\left\lfloor\frac{n}{5}\right\rfloor}} 的最后一位容易计算。

所以 f(n) 就能计算了。

因为要高精度，于是我用了 Python 实现。

Code:

a=[6,2,6,4,4,4,8,4,6,6]
sm=[1,2,6,4,2,2,4,2,8,8]
t=[2,6,8,4]
def geta(n):
    if n==1:
        return 1
    else:
        return a[(n-1)%10]
def gets(n):
    last=geta(n)
    id=t.index(last)
    return t[(id+(n//5))%4]
def f(n):
    if n<=10:
        return sm[n-1]
    else:
        return (gets(n)*f(n//5))%10
def testt(n):
    s=1
    for i in range(2,n+1):
        s=s*i
    return s
fl=True
while fl:
    try:
        n=int(input())
        print(f(n))
    except:
        fl=False

再见，qwq~