Big Number
Time Limit: 20000/10000 MS (Java/Others) Memory
Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2768 Accepted Submission(s): 1276
Problem 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
≤ n ≤ 107 on each line.
Output
The output contains the number of digits in the factorial of the integers appearing in the input.
Sample Input
Sample Output
题目的大意是说给定一个数并且这个数有可能很大，求这个数阶乘后的位数。
log10(n!)=log10(1*2*3…*n)=log10(1)+log10(2)+…+log10(n)，这个公式当时看的时候想不明白，为什么取以10为底的对数就是这个数的位数，其实看log10(10)就明白了，这个数值是1，而位数正好就增加1。对log10(n!)的值取整加1就是n!的位数。n这个数如果不大的话这样做，10^7的话这样做肯定超时的。需用斯特林公式：
log10(n!) = log10(sqrt(2 * pi * n)) + n * log10(n / e)
当n>3的时候这个公式成立。当n<=3的时候位数为1。
在杭电上提交用第一个公式就能ac，代码如下：
#include<iostream>
#include<cmath>
using namespace std;
int digit(int number)
{
int i;
double sum=0;
for(i=1;i<=number;i++)
sum+=log10(double(i));//根据公式得来的
sum=floor(sum)+1;//向下取整函数
return sum;
}
int main()
{
int num;
cin>>num;
while(num--)
{
int dig;
cin>>dig;
cout<<（int）digit(dig)<<endl;
}
return 0;
}
但是在北大上就TLE错误，只好用斯特林公式去做，ac。
代码如下：
#include<iostream>
#include<cmath>
using namespace std;
int digit(int number)
{
double PI=acos(double(-1));//获取PI的值，原来还不知道有这个公式，对-1取反余弦函数。
double e=exp(double(1));//获取自然底数e的值
return int(log10(sqrt(2*PI*number))+number*log10(number/e))+1;
}
int main()
{
int num;
cin>>num;
while(num--)
{
int dig;
cin>>dig;
cout<<(int)digit(dig)<<endl;
}
return 0;
}
转播
