描述

题目链接

夫夫有一天对一个数有多少位数感兴趣，但是他又不想跟凡夫俗子一样，所以他想知道给一个整数n，求n！的在8进制下的位数是多少位。

Input

第一行是一个整数t(0<t<=1000000)(表示t组数据)
接下来t行，每一行有一个整数n(0<=n<=10000000)

Output

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

Examples

intput
1
2
3
4
3
4
2
5
output
1
2
3
2
1
3

思路

看到n的值最大是1e7就知道不能暴力出奇迹，而求n!的位数，就很自然想到要用斯特林公式:
$n!\approx\sqrt{2\pi n}(\frac{n}{e})^n$

虽然斯特林公式只是求阶乘的近似值，但即使在n很小的时候，斯特林公式的取值已经十分准确。

再求以8为底近似值的对数 +1(求其他进制下的位数类似，修改底数即可)。

注意:C语言中不支持任意底数的求对数运算，我们小小的转换一下$\log_x y=\frac{lgy}{lgx}$

代码

#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>  
#include<string.h>  
#include<string>   
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
using namespace std;
const double Pi = acos(-1);
const double e = 2.718281828459;
int main()
{
    int t,n;
	scanf("%d",&t);    
	while(t--)    
	{        
		scanf("%d",&n);
		if(n==0||n==1)	//注意特判 
			printf("1\n");
		else        
		printf("%d\n",(int)((log(2.0*Pi*n)/(log(8))/2.0 + n*log(n/e)/log(8))+1));
	}
	return 0;
}