HDU 1018 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

2
10
20
        

Sample Output

7
19
  
  

        

本題就考查斯特林公式。因為斯特林公式是求解n！的近似公式，而本題隻需要求解有多少位。

底層數學原理就是求一個數n的數位可以使用 digits = log10(n)

然後利用斯特林公式求出n！的近似值就可以利用log10來求得數位了。

斯特林公式百度百科有，這裡不重複了。

float不能AC的時候，就使用double吧。

#include <stdio.h>
#include <math.h>
const float PI = 3.14159265358979323846f;

inline int getDigits(int n)
{
	float num = float(n);
	int ans = (int)(0.5*log10(2.0*PI*num) + num*(log(num)-1)/log(10.0)) + 1;
	return ans;
}

int main()
{
	int T, n;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d", &n);
		printf("%d\n", getDigits(n));
	}
	return 0;
}