HDU 1018 Big Number (數的階乘的長度：數學)

Big Number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 34415    Accepted Submission(s): 16289

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

2
10
20
        

Sample Output

7
19
        

Source Asia 2002, Dhaka (Bengal)

Recommend JGShining   |   We have carefully selected several similar problems for you:  1071 1020 1009 1065 1042 

題意：求一個數的階乘的長度。

題解：任意一個正整數a的位數

等于(int)log10(a) + 1；推導一下：

  對于任意一個給定的正整數a，

  假設10^(x-1)<=a<10^x，那麼顯然a的位數為x位，

  又因為

  log10(10^(x-1))<=log10(a)<(log10(10^x))

  即x-1<=log10(a)<x

  則(int)log10(a)=x-1,

  即(int)log10(a)+1=x

  即a的位數是(int)log10(a)+1

我們知道了一個正整數a的位數等于(int)log10(a) + 1，

現在來求n的階乘的位數：

假設A=n!=1*2*3*......*n，那麼我們要求的就是

(int)log10(A)+1，而：

log10(A)

        =log10(1*2*3*......n)  （根據log10(a*b) = log10(a) + log10(b)有）

        =log10(1)+log10(2)+log10(3)+......+log10(n)

也就是将求n的階乘的位數分解成了求n個數對10取對數的和，并且對于其中任意一個數，都在正常的數字範圍之類。

總結一下：n的階乘的位數等于

 (int)(log10(1)+log10(2)+log10(3)+......+log10(n)) + 1。

AC代碼:

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
	int n,i,T;
	double sum;
	cin>>T;
	while(T--){
		cin>>n;
		sum=0.0;
		for(i=2;i<=n;i++){
			sum+=log10(i);
		}
		cout<<(int)sum+1<<endl;
	}
	return 0;
}