杭電--1018 Big Number

本題リンク:クリックしてリンクを開く
Big Number
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 37508    Accepted Submission(s): 18024
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 
   
 
  

题意：先给出一个整数n,表示有n组测试数据，接着是有n个数据，每一个数据都是介于1到10⁷之间。要求的是每个数阶层的位数，也就是每个数字阶层的长度是多少？

解题思路：

1.直接暴力求解，但似乎数据真的实在是太大了，但只要稍微改进一下代码还是可以AC的，只是比较费时，本人用了889MS险过；由于数据比较大，所以得用double类型，有时候这也是一个小技巧。

代码1：

#include 
#include 
int main()
{
    int t,i,k,n;
    double w;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        s=1;
        w=1;
        for(i=2; i<=n; i++)
        {
            s=s*i;
            if(s>=10)			//       10 ，        ，      for     ，       。
                while(s>=10)
                {
                    s/=10;
                    w++;		//      。
                }
        }
        printf("%d
",w);
    }
    return 0;
}

2.本題の特性を利用して数桁で解いて、まず私達の知っている1つの知識点、それはつまり
任意の正の整数aのビット数は(int)log 10(a)+1に等しい.
任意の与えられた正の整数aについて、導出については参考にすることができます:(詳細はリンクをクリックしてください)http://www.wendangku.net/doc/b2ca872014791711cd79170b.html)
10^(x-1)<=a<10^xとすると、明らかにaのビット数はxビットであり、またlog 10(10^(x-1))<=log 10(a)すなわちx-1<=log 10(a)である(int)log 10(a)=x-1である(int)log 10(a)+1=xである(int)log 10(a)+1である.
コード2.

#include 
#include 
#include 
int main()
{
    int t,i,n;
    double w;
    scanf("%d",&t);
    while(t--)
    {
            scanf("%d",&n);
            w=1;
            for(i=1;i<=n; i++)
            w=w+log10((double)i);
        printf("%d
",(int) w);
    }
    return 0;
}

3.最近では、log 10(n!)=1.0/2*log 10(2*PI*n)+n*log 10(n/e);なぜ来たのかについては、興味のある友达は自分で資料を調べることができます.そうしないと、記憶がよくなります.前の2つ目の方法と同じように、公式があれば簡単です.
コード3:

#include 
#include 
#include 
#define e 2.71828182
#define PI 3.141592654
int main()
{
    int t;
    int n;
    double w;             //    
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        w=(1.0/2*log10(2*PI*n)+n*log10(n/e));
        printf("%d
",(int) w+1);              //  +1，   。
    }
    return 0;
}

以上の3つの方法は私が推薦したのは2つ目と3つ目で、2つの公式はみんながどのように来たのかを細かく調べる必要はありませんが、必ずそれを覚えておいてください.肝心な時はとても役に立ち、友达を助けることができることを望んでいます.