中山优化网站,手机网站 html,爱链接,实时热搜C.idol!!
数学
题目大意
正整数 n n n 的双阶乘 n ! ! n!! n!! 表示不超过 n n n 且与 n n n 有相同奇偶性的所有正整数乘积 求对于给定 n n n #xff0c; ∏ i 1 n i ! ! \prod\limits_{i1}^n i!! i1∏ni!! 的后缀 0 0 0 个数
解题思路
根据双阶乘的性质…C.idol!!
数学
题目大意
正整数 n n n 的双阶乘 n ! ! n!! n!! 表示不超过 n n n 且与 n n n 有相同奇偶性的所有正整数乘积 求对于给定 n n n ∏ i 1 n i ! ! \prod\limits_{i1}^n i!! i1∏ni!! 的后缀 0 0 0 个数
解题思路
根据双阶乘的性质可以得到 ( n − 1 ) ! ! × n ! ! n ! (n-1)!!\times n!!n! (n−1)!!×n!!n! 因此对于给定的 n n n 原式可化为 ∏ i 1 n i ! ! { ∏ i 1 n 2 ( 2 i ) ! , n 为偶数 ∏ i 1 n 1 2 ( 2 i − 1 ) ! , n 为奇数 \prod\limits_{i1}^n i!!\begin{cases} \prod\limits_{i1}^\frac{n}{2} (2i)! ,n为偶数 \\ \prod\limits_{i1}^\frac{n1}{2} (2i-1)! ,n为奇数 \end{cases} i1∏ni!!⎩ ⎨ ⎧i1∏2n(2i)!i1∏2n1(2i−1)!,n为偶数,n为奇数 显而易见的阶乘中因子 2 2 2 的个数一定多于因子 5 5 5 的个数因此题目等价于求上式中因子 5 5 5 的个数//
考虑某单一阶乘 n ! n! n! 中所含因子 5 5 5 的个数。 可以发现每个 5 5 5 的倍数项会提供 1 1 1 个因子 5 5 5 共有 ⌊ n 5 ⌋ \lfloor \dfrac{n}{5} \rfloor ⌊5n⌋ 项 除此之外每个 25 5 2 255^2 2552 的倍数项会额外提供一个因子 5 5 5 共有 ⌊ n 5 2 ⌋ \lfloor \dfrac{n}{5^2} \rfloor ⌊52n⌋ 项 再除此之外每个 125 5 3 1255^3 12553 的倍数项会额外提供一个因子 5 5 5 共有 ⌊ n 5 3 ⌋ \lfloor \dfrac{n}{5^3} \rfloor ⌊53n⌋ 项…… 因此对于单一阶乘 n ! n! n! 其提供因子 5 5 5 的数量 c n t 5 ∑ i 1 N ⌊ n 5 i ⌋ ( 5 N n ) cnt_5\sum\limits_{i1}^N \lfloor \dfrac{n}{5^i} \rfloor (5^Nn) cnt5i1∑N⌊5in⌋(5Nn)
接着考虑连乘积中因子 5 5 5 个数的总和。 a n s { ∑ i 1 n 2 ∑ j 1 N ⌊ 2 i 5 j ⌋ ∑ i 1 N ∑ j 1 n 2 ⌊ 2 j 5 i ⌋ , n 为偶数 ∑ i 1 n 1 2 ∑ j 1 N ⌊ 2 i − 1 5 j ⌋ ∑ i 1 N ∑ j 1 n 1 2 ⌊ 2 j − 1 5 i ⌋ , n 为奇数 ans\begin{cases} \sum\limits_{i1}^\frac{n}{2} \sum\limits_{j1}^N \lfloor \dfrac{2i}{5^j} \rfloor\sum\limits_{i1}^N \sum\limits_{j1}^\frac{n}{2} \lfloor \dfrac{2j}{5^i} \rfloor ,n为偶数 \\ \sum\limits_{i1}^\frac{n1}{2} \sum\limits_{j1}^N \lfloor \dfrac{2i-1}{5^j} \rfloor\sum\limits_{i1}^N \sum\limits_{j1}^\frac{n1}{2} \lfloor \dfrac{2j-1}{5^i} \rfloor ,n为奇数 \end{cases} \\ ans⎩ ⎨ ⎧i1∑2nj1∑N⌊5j2i⌋i1∑Nj1∑2n⌊5i2j⌋i1∑2n1j1∑N⌊5j2i−1⌋i1∑Nj1∑2n1⌊5i2j−1⌋,n为偶数,n为奇数
对于某一 i i i 发现不论 n n n 的奇偶 j 1 j1 j1 开始的每 5 i 5^i 5i 项之和构成公差为 2 × 5 i 2\times5^i 2×5i 的等差数列// 例 i 1 i1 i1 n n n 为偶数且足够大时 ⌊ 2 j 5 i ⌋ \lfloor \dfrac{2j}{5^i} \rfloor ⌊5i2j⌋ 的前 15 15 15 项如下其中每 5 5 5 项之和构成公差为 5 × 2 5\times 2 5×2 的等差数列 0 , 0 , 1 , 1 , 2 ∣ ∣ 2 , 2 , 3 , 3 , 4 ∣ ∣ 4 , 4 , 5 , 5 , 6 … … 0,0,1,1,2||2,2,3,3,4||4,4,5,5,6…… 0,0,1,1,2∣∣2,2,3,3,4∣∣4,4,5,5,6……
经计算对于某一 i i i 等差数列的首项为 a 1 { ⌊ 5 i 2 ⌋ 2 , n 为偶数 ⌊ 5 i 2 ⌋ 1 , n 为奇数 a_1\begin{cases} \lfloor \dfrac{5^i}{2} \rfloor2 ,n为偶数 \\ \lfloor \dfrac{5^i}{2} \rfloor1 ,n为奇数 \end{cases} a1⎩ ⎨ ⎧⌊25i⌋2⌊25i⌋1,n为偶数,n为奇数
完整的段用等差数列求和非完整的段手算一下// 若此前完整段的数量记为 m m m 则非完整段 前 ⌊ 5 i 2 ⌋ \lfloor \dfrac{5^i}{2} \rfloor ⌊25i⌋ 项的值为 2 m 2m 2m 第 ⌊ 5 i 2 ⌋ 1 \lfloor \dfrac{5^i}{2} \rfloor1 ⌊25i⌋1 至 $2\times\lfloor \dfrac{5^i}{2} \rfloor $ 项的值为 2 m 1 2m1 2m1手搓一下就知道了
求和即可
令 N ⌊ log 5 n ⌋ 1 N\lfloor \log_5n \rfloor1 N⌊log5n⌋1 对 i ∈ [ 1 , N ] i\in[1,N] i∈[1,N] 遍历求和得到答案
由于答案数据极其庞大超出了C %lld(64bits)的范围因此需要使用更高位数的整数类型如int128//或者直接转战Python
时间复杂度 O ( log n ) O(\log n) O(logn)
参考代码
import math
# while 1:
nint(input())
Nint(math.log(n,5)1)
re0
if n%20 :for i in range(1,N1) :#print(istr(i))a1(5**i)//22 #首项#print(a1str(a1))d(5**i)*2 #公差#print(dstr(d))m(n//2)//(5**i) #完整段数#print(mstr(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 :ren//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,N1) :#print(istr(i))a1(5**i)//21 #首项#print(a1str(a1))d(5**i)*2 #公差#print(dstr(d))m((n1)//2)//(5**i) #完整段数#print(mstr(m))re(2*a1(m-1)*d)*m//2 #完整段等差数列求和#print(re1: str(re))re((n1)//2-m*(5**i))*2*m #最后一段余项求和#print(re2: str(re)) #print(pl1 str(((n1)//2-m*(5**i))*2*m))if (n1)//2-m*(5**i)(5**i)//2 :re(n1)//2-m*(5**i)-(5**i)//2#print(pl2 str((n1)//2-m*(5**i)-(5**i)//2))print(re)
