C.idol!!

数学

题目大意

正整数 $nn$ 的双阶乘 $n!!n!!$ 表示不超过 $nn$ 且与 $nn$ 有相同奇偶性的所有正整数乘积 求对于给定 $nn$ ，${\prod }_{i=1}^{n}i!!\backslash prod\backslash limits\_\{i=1\}^n\; i!!$ 的后缀 $00$ 个数

解题思路

蒟蒻一枚//只能用最原始的思考方法qwq稍微有那么亿些复杂

根据双阶乘的性质，可以得到： $(n-1)!!\times n!!=n!(n-1)!!\backslash times\; n!!=n!$

因此对于给定的 $nn$ ，原式可化为：

显而易见的，阶乘中因子 $22$ 的个数一定多于因子 $55$ 的个数，因此题目等价于求上式中因子 $55$ 的个数//

考虑某单一阶乘 $n!n!$ 中所含因子 $55$ 的个数。

可以发现，每个 $55$ 的倍数项会提供 $11$ 个因子 $55$ ，共有 $\lfloor {\displaystyle \frac{n}{5}}\rfloor \backslash lfloor\; \backslash dfrac\{n\}\{5\}\; \backslash rfloor$ 项 除此之外每个 $25=5^{2}25=5^2$ 的倍数项会额外提供一个因子 $55$ ，共有 $\lfloor {\displaystyle \frac{n}{5^2}}\rfloor \backslash lfloor\; \backslash dfrac\{n\}\{5^2\}\; \backslash rfloor$ 项

再除此之外每个 $125=5^{3}125=5^3$ 的倍数项会额外提供一个因子 $55$ ，共有 $\lfloor {\displaystyle \frac{n}{5^3}}\rfloor \backslash lfloor\; \backslash dfrac\{n\}\{5^3\}\; \backslash rfloor$ 项……

因此对于单一阶乘 $n!n!$ ，其提供因子 $55$ 的数量 $cn{t}_5={\sum }_{i=1}^N\lfloor {\displaystyle \frac{n}{5^i}}\rfloor (5^N>n)cnt\_5=\backslash sum\backslash limits\_\{i=1\}^N\; \backslash lfloor\; \backslash dfrac\{n\}\{5^i\}\; \backslash rfloor\; (5^N>n)$

接着考虑连乘积中因子 $55$ 个数的总和。

对于某一 $ii$ ，发现不论 $nn$ 的奇偶， $j=1j=1$ 开始的每 $5^{i}5^i$ 项之和构成公差为 $2\times 5^{i}2\backslash times5^i$ 的等差数列//

例：$i=1i=1$ ，$nn$ 为偶数且足够大时，$\lfloor {\displaystyle \frac{2j}{5^i}}\rfloor \backslash lfloor\; \backslash dfrac\{2j\}\{5^i\}\; \backslash rfloor$ 的前 $1515$ 项如下，其中每 $55$ 项之和构成公差为 $5\times 25\backslash times\; 2$ 的等差数列： $0,0,1,1,2\mathrm{\mid }\mathrm{\mid }2,2,3,3,4\mathrm{\mid }\mathrm{\mid }4,4,5,5,6\dots \dots 0,0,1,1,2||2,2,3,3,4||4,4,5,5,6\dots \dots$

经计算，对于某一 $ii$ ，等差数列的首项为

完整的段用等差数列求和，非完整的段手算一下//

若此前完整段的数量记为 $mm$ ，则：

非完整段前 $\lfloor {\displaystyle \frac{5^i}{2}}\rfloor \backslash lfloor\; \backslash dfrac\{5^i\}\{2\}\; \backslash rfloor$ 项的值为 $2m2m$ ，

第 $\lfloor {\displaystyle \frac{5^i}{2}}\rfloor +1\backslash lfloor\; \backslash dfrac\{5^i\}\{2\}\; \backslash rfloor+1$ 至 $2\times \lfloor {\displaystyle \frac{5^i}{2}}\rfloor 2\backslash times\backslash lfloor\; \backslash dfrac\{5^i\}\{2\}\; \backslash rfloor$ 项的值为 $2m+12m+1$（手搓一下就知道了），

求和即可

令 $N=\lfloor {}_{5}n\rfloor +1N=\backslash lfloor\; \backslash log\_5n\; \backslash rfloor+1$ ，对 $i\in [1,N]i\backslash in[1,N]$ 遍历求和得到答案

由于答案数据极其庞大，超出了C++ %lld(64bits)的范围，因此需要使用更高位数的整数类型（如int128）//或者直接转战Python

时间复杂度

$O(\log n)O(\backslash log\; n)$

参考代码

import math
# while 1:
n=int(input())
N=int(math.log(n,5)+1)
re=0
if n%2==0 :
    for i in range(1,N+1) :
        #print("i="+str(i))
        a1=(5**i)//2+2 #首项
        #print("a1="+str(a1))
        d=(5**i)*2 #公差
        #print("d="+str(d))
        m=(n//2)//(5**i) #完整段数
        #print("m="+str(m))
        re+=(2*a1+(m-1)*d)*m//2 #完整段等差数列求和
        #print("re1:" + str(re))
        re+=(n//2-m*(5**i))*2*m #最后一段余项求和
        #print("re2:" + str(re))
        #print("pl1=" + str((n//2-m*(5**i))*2*m))
        if n//2-m*(5**i)>(5**i)//2 :
            re+=n//2-m*(5**i)-(5**i)//2
            #print("pl2=" + str(n//2-m*(5**i)-(5**i)//2))
                

if n%2 :
    for i in range(1,N+1) :
        #print("i="+str(i))
        a1=(5**i)//2+1 #首项
        #print("a1="+str(a1))
        d=(5**i)*2 #公差
        #print("d="+str(d))
        m=((n+1)//2)//(5**i) #完整段数
        #print("m="+str(m))
        re+=(2*a1+(m-1)*d)*m//2 #完整段等差数列求和
        #print("re1:" + str(re))
        re+=((n+1)//2-m*(5**i))*2*m #最后一段余项求和
        #print("re2:" + str(re)) 
        #print("pl1=" + str(((n+1)//2-m*(5**i))*2*m))
        if (n+1)//2-m*(5**i)>(5**i)//2 :
            re+=(n+1)//2-m*(5**i)-(5**i)//2
            #print("pl2=" + str((n+1)//2-m*(5**i)-(5**i)//2))
    
print(re)