题目

Description

给出一个整数，确定这个数的阶乘的位数。

Input

多组数据，每行为一个大于等于1且小于等于107的整数n.

Output

对应每个输入数据输出一个结果。

Sample Input

10
20

Sample Output

7
19

题解

两种方法可能可以实现：

• 抛去一定的精度来计算
• 采用数学公式计算

抛去一定的精度来计算

对于第一种方法，我们可以得知，对于两个大数相乘，其较低位对结果的影响较小，因此我们可以舍弃一些数据

采用类似于科学记数法的形式来计算(a*10^b)

这种做法，当n较大时，会由于误差的累积导致错误。

采用数学公式计算

而第二种方法可以采用一些数学公式计算

log10n! = log10(1*2*3*......*n) = log101+log102+log103+...+log10n

显然，等式右侧我们可以轻易得出。

而等式左侧，log10n的意义是n对10的对数，即10log10n=n

对于一个整数k，若10k<n<10k+1，我们可以得出结论，n是k位数

所以，大数n!的位数就是log10n!，由于int的向下取整性质，我们还要将这个数再加上1

虽然题目上说的最大值是107，然而，最大值至少是197(方法1WA)

代码

/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/
 
かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
using namespace std;
 
//DEBUG MODE
#define debug 0
 
 
const int maxn = 10005;
bool tree[maxn];
 
int bit(int n) {
    int a = 1;
    int e = 0;
 
    for(int i = 1;i <= n;i++) {
        a *= i;
        while(a / 100000) {//保证精度
            a /= 10;
            e++;
        }
    }
 
    while(a) {//转化为位数
        a /= 10;
        e++;
    }
 
    return e;
}
 
//n! = 1*2*3*4*5*......*(n-1)*n
//ln n! = ln 1+len2+......ln(n-1)+ln n
int mathbit(int n) {
    double ans = 0;
    for(int i = 1;i <= n;i++)
        ans += log10(i);
    return (int)ans+1;
}
 
 
bool Do() {
    int n;
    if(scanf("%d",&n) == EOF)
        return false;
 
 
    printf("%d\n",mathbit(n));
    return true;
}
 
int main() {
    while(Do());
    return 0;
}