HDU 1018.Big Number【7月25】

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的階乖的位數等于LOG10（N！）＝LOG10（1）＋.....LOG10（N）。ok，上代碼：

#include<cstdio>
#include<cmath>
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int x;
        double sum=0;
        scanf("%d",&x);
        for(int j=1;j<=x;j++)
            sum+=log10(j);
        printf("%d\n",int(sum)+1);
    }
    return 0;
}
           

同時又找到一點資料：Stirling公式：n!與√(2πn) * n^n * e^(-n)的值十分接近

故log10(n!) = log(n!) / log(10) = ( n*log(n) - n + 0.5*log(2*π*n))/log(n);

下面是别人的代碼：

#include <stdio.h>
#include <math.h>

const double PI = acos(-1.0);
const double ln_10 = log(10.0);

double reback(int N)
{
    return ceil((N*log(double(N))-N+0.5*log(2.0*N*PI))/ln_10);
}    

int main()
{
	int cas,n;
	scanf("%d",&cas);
	while(cas--)
	{
		scanf("%d",&n);
		if(n<=1)printf("1\n");
		else printf("%.0lf\n",reback(n));
	}
	return 0;
}
           

真的漲姿勢！