题意:给一个数n,计算n的阶乘有多少位数。


方法一:

由于给出的n很大,到了10^7,所以直接计算是肯定不可能的,所以可以使用log。

例如:log10(100) = 2;log10(1000)=3,log10(54321)~4.7,log10(12345)~4.0...

我们可以看出,以10为底计算log10(x)向下取整就是这个数的位数-1,

而:log10(n!)=log10(n*(n-1)*...*1)=log10(n)+log10(n-1)+...+log10(1)。


方法二:

使用斯特林公式:

blob.png


题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1018


代码:

Memory: 1804 KB
Time: 374 MS
Language: C++
Result: Accepted


#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    int n, x;
    double ans;
    cin>>n;
    while(n--){
        cin>>x;
        ans=1;
        for(int i=1;i<=x;i++)ans+=log10(i);
        cout<<(int)ans<<endl;
    }
    return 0;
}
Memory: 1804 KB
Time: 0 MS
Language: C++
Result: Accepted
#include <iostream>
#include <cmath>
using namespace std;
const double pi = acos(-1.0);
const double e = 2.7182818;
int main()
{
    int x, n, ans;
    cin>>x;
    while(x--){
        cin>>n;
        if(n)ans = int(log10(2*pi*n)/2+n*(log10(n)-log10(e))) + 1;
        else ans=1;
        cout<<ans<<endl;
    }
    return 0;
}
Memory: 9480 KB
Time: 795 MS
Language: Java
Result: Accepted
import java.util.*;
import java.lang.Math;
public class Main {
    public static void main(String[] args){
        Scanner cin = new Scanner(System.in);
        int x, n;
        double ans;
        n = cin.nextInt();
        for(int k=0;k<n;k++){
            ans = 1;
            x = cin.nextInt();
            for(int i=1;i<=x;i++)ans+= Math.log10(i);
            int ansi = (int)ans;
            System.out.println(ansi);
        }
    }
}