题目描述：
Description
In many applications very large integers numbers are required. Some of these applications are using keys for secure transmission of data, encryption, etc. In this problem you are given a number, you have to determine the number of digits in the factorial of the number.
Input
Input consists of several lines of integer numbers. The first line contains an integer n, which is the number of cases to be tested, followed by n lines, one integer 1 <= m <= 10^7 on each line.
Output
The output contains the number of digits in the factorial of the integers appearing in the input.
Sample Input
2
10
20
Sample Output
7
19
分析：输入n个数，每个数m都可能很大，要求输出m!的位数，比如说10！=2628800，那么输出就是7。
解法一(该方法在PKU上会TLE，原因是其复杂度为o(n) )：
由于n!=n*(n-1)*……*2*1 = 10^dn * 10^dn-1 *……* 10^di*……10^d0 = 10^(dn+dn-1+……+d0);其中：dn = log10(n),dn-1 = log10(n-1)……
因此，n!的位数其实就是dn+……+di+……+d0；因此可以得到如下代码：
#include "iostream"
#include "cmath"
using namespace std;
int main(int argc, char* argv[])
{
int N;
int Num;
cin>>N;
double d ;
for (int i =0;i<N;i++)
{
cin>>Num;
d =1;
for (int j=2;j<=Num;j++)
{
d +=log10(j);
}
cout<<(int)d<<endl;
}
return 0;
}
解法二：stirling公式，复杂度O(1)，PKU上通过
假设n！ = 10^d;其中d可能包含小数，但是d的整数部分就是n！的位数
由stirling公式：n!~((n/e)^n )* (2* pi * n)^(1/2);则： d = log10(n!) = n*log10(n/e) + 0.5*log10(2*pi*n);于是得到如下代码：
#include "iostream"
#include "cmath"
using namespace std;
const double pi = 3.1415926535898;
const double e = 2.718281828459;
int main(int argc, char* argv[])
{
int N;
int Num;
cin>>N;
for (int i =0;i<N;i++)
{
cin>>Num;
cout<<(int)(Num*log10(Num / e) + 0.5*log10(2*pi*Num)) +1<<endl;
}
return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
