AOJ 758.大数的位数

185


题目



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;
}
发布评论
  • 点击查看/关闭被识别为广告的评论