ステップ乗算
Big Number
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 ≤ 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
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 ≤ 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
题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1018
题意大意：输入n，问n的阶乘是几位数。
解题思路：这题n的范围最大到107，所以肯定不能用常规的方法求n!，甚至可能没有必要求。在这里，我要介绍一下斯特林定理（粗略介绍）。
具体公式：n!≈√(2πn)(n/e)n
我们对等号两边同时取以10为底的对数，则可得：（设k为n!的位数）
k-1 =log10(n!)= log10(√(2πn))+nlog10(n/e)
k为什么要减1呢？很简单，log10(10) = 1，但是10是两位数，所以我们所求的位数与实际相差1.
辅助知识:
log10(a*b) = log10(a) + log10(b)
log10(a/b) = log10(a) - log10(b)
源代码如下：
#include
#include
using namespace std;
#define Pi 3.14159265
#define e 2.71828182
int main(void)
{
int cas,n;
double digit;
scanf("%d",&cas);
while(cas--)
{ scanf("%d",&n);
digit = log10(sqrt(2*Pi*n))+n*log10(n/e);//
printf("%d
",(int)digit+1); // k-1 1 1
}
return 0;
}