解题思路

这道题目要求计算给定数字$m$的阶乘$m!$的位数。由于$m$的范围可以达到$10^7$，直接计算$m!$的值显然不可行，因为$m!$会极其庞大，超出普通数据类型的表示范围。因此，我们需要使用数学方法来间接计算$m!$的位数。

关键数学知识：斯特林公式（Stirling's Formula）

斯特林公式提供了阶乘的一个近似表达式：

$$n! \approx \sqrt{2 \pi n} \left( \frac{n}{e} \right)^n $$

取对数后可以转换为：

$$\log_{10}(n!) \approx \log_{10}(\sqrt{2 \pi n}) + n \log_{10}\left(\frac{n}{e}\right) $$

由于一个数的位数可以通过其对数加1后取整得到，因此$n!$的位数$D$可以近似为：

$$D = \lfloor \log_{10}(n!) \rfloor + 1$$

步骤分解

1. 输入处理：读取测试用例的数量$n$，然后逐个读取每个测试数字$num$。
2. 特殊情况处理：如果$num = 1$，直接输出$1$，因为$1! = 1$只有1位。
3. 斯特林公式应用：
   • 计算$\log_{10}(\sqrt{2 \pi num})$。
   • 计算$num \cdot \log_{10}\left(\frac{num}{e}\right)$。
   • 将两部分相加后加1，并取整得到位数。
4. 输出结果：对每个测试数字，输出计算得到的位数。

代码解释

• 数学库函数：使用log10计算以10为底的对数，sqrt计算平方根，exp(1.0)表示自然常数$e$，acos(-1.0)表示圆周率$\pi$。
• 公式转换：代码中的表达式log10(sqrt(2 * pi * num)) + num * log10(num / e)直接对应斯特林公式的对数形式，最后加1并取整得到位数。

复杂度分析

• 时间复杂度：每个测试用例的计算是$O(1)$，总复杂度为$O(n)$，其中$n$是测试用例的数量。对于$n \leq 10^7$，这是非常高效的。
• 空间复杂度：$O(1)$，仅使用常数级别的额外空间。

这种方法避免了直接计算大数阶乘，通过数学近似高效地解决了问题。

#include <iostream>
#include <cmath>
using namespace std;
const double pi = acos(-1.0);	
const double e = exp(1.0);		
int main()
{
	int n;
	long num;
	cin >> n;
	for(int i = 0; i < n; i++)
	{
		cin >> num;
		if(num == 1)
			cout << 1 << endl;
		else
			cout << int (log10(sqrt(2 * pi * num)) + num * log10(num / e) + 1) << endl;		
	}
	return 0;
}