题解 | #不凡的夫夫#

题目描述

夫夫有一天对一个数有多少位数感兴趣，但是他又不想跟凡夫俗子一样,

所以他想知道给一个整数n，求n！的在8进制下的位数是多少位。

输入描述:

第一行是一个整数t(0<t<=1000000)(表示t组数据)

接下来t行，每一行有一个整数n(0<=n<=10000000)

输出描述:

输出n！在8进制下的位数。

题解：

n的阶乘可以用斯特林公式来近似替代:$n!\approx \sqrt{2\pi n}(\frac{n}{e}{)}^{n}n!\backslash approx\backslash sqrt\{2\backslash pi\; n\}(\backslash frac\{n\}\{e\})^\{n\}$

这个公式不懂的可以去查一下。

又因为这道题是求n!在八进制下位数是多少位，其实只需要以8为底，求n!对数，然后取整再+1就好了,也可以用ceil()。

最后简单的对数运算:$n!\approx \sqrt{2\pi n}(\frac{n}{e}{)}^n=\frac{1}{2}{}_8(2\pi n)+n({}_{8}n-lo{g}_{8}e)n!\backslash approx\backslash sqrt\{2\backslash pi\; n\}(\backslash frac\{n\}\{e\})^\{n\}=\backslash frac\{1\}\{2\}\backslash log\_8(2\backslash pi\; n)+n(\backslash log\_8n-log\_8e)$

代码:

#include <iostream>
#include <cmath>

#define LL long long

using namespace std;

const double e = exp(1);
const double PI = acos(-1.0);


LL sum, n;

double log8(double x)//返回以8为底x的对数；
{
	return log(x) / log(8);
}

int main()
{
	int T; scanf("%d", &T);

	while (T--)
	{
		scanf("%d", &n);
		if (n <= 3)printf("1\n");//3!=6;所以n小于3的时候直接输出一就行，减少时间复杂度
		else
		{
			sum = (long long)(ceil(log8(2 * PI * n) / 2 + n * (log8(1.00 * n) - log8(e))));
			printf("%lld\n", sum);
		}
	}return 0;
}