[语言月赛202305C] 计算阶乘 2 题解

· · 题解

[语言月赛202305C] 计算阶乘 2 题解

Source & Knowledge

2023 年 5 月语言月赛，由洛谷网校入门计划/基础计划提供。

本题考查简单循环。

文字题解

题目大意

定义

n!! = \begin{cases} n \times (n - 2) !!, & n \geq 2 \\ 1, &n = 0, 1\end{cases}

求 2 \times \frac{n!}{n!!}。

### 解析 分析式子： $n! = n \times (n - 1) \times (n - 2) \times (n - 3) \times \dots n!! = n \times (n - 2) \times (n - 4) \times (n - 6) \times \dots \frac{n!}{n!!} = \frac{n \times (n - 1) \times (n - 2) \times (n - 3) \times \dots}{n \times (n - 2) \times (n - 4) \times (n - 6) \times \dots}

可以发现，n!! 的每个因式都是 n! 的因式，会被直接约分掉。例如，分数线上下 n 都出现了，可以约分；n - 2 都出现了，可以约分……

约分结束后，分母为 1，分子为 (n - 1) \times (n - 3) \times (n - 5) \times \dots \times 1

我们只需要用一个循环计算上式，最后乘上 2 即可。

注意到答案小于 2^{64} 但是大于 2^{63} 次方。long long 所能存储的最大正数为 2^{63} - 1，所以不能使用 long long 存储答案，而应该使用 unsigned long long。这一类型不能表示负数，但是可以表示的最大正数是 2^{64} - 1，答案在这一范围内。

unsigned long long ans = 2;
for (int i = n - 1; i > 1; i -= 2) {
  ans = ans * i;
}

视频题解