斯特林(Stirling)公式求大数阶乘的位数


我们知道整数n的位数的计算方法为：log10(n)+1
n!=10^m
故n!的位数为 m = log10(n!)+1

lgN！=lg1+lg2+lg3+lg4+lg5+....................+lgN;

但是当N很大的时候，我们可以通过数学公式进行优化：（即Stirling公式）

N！=sqrt（2*pi*N）*（N/e）^N；（pi=3.1415926=acos（-1.0），e=exp(1)）

lgN！=(lg(2*pi)+lgN)/2+N*(lgN-lge);

斯特林公式可以用来估算某数的大小结合lg可以估算某数的位数，或者可以估算某数的阶乘是另一个数的倍数。

例题

https://www.nowcoder.net/acm/contest/75/A

题意求解n的阶乘八进制下的位数

n!=8^res n!=e^m

res=log8(n!) m=loge(n!)

log8(n!)= loge(n!)/loge(8) res = m/loge(8)换底公式

m=loge(2*pi*n)/2+n*loge(n/e)

AC代码

#include <stdio.h>

#include <math.h>

#include <string.h>

#include <stdlib.h>

#include <iostream>

#include <sstream>

#include <algorithm>

#include <string>

#include <queue>

#include <map>

#include <vector>

using namespace std;

const int maxn = 1e6+;

const int inf = 0x3f3f3f3f;

const double e = exp();

const double pi = acos(-1.0);

const double epx = 1e-;

typedef long long ll;

int main()

{

    ll t;

    scanf("%lld",&t);

    while(t--){

        ll n;

        scanf("%lld",&n);

        if(n==||n==){

            puts("");

            continue;

        }

        double res = (log(*pi*n)/2.0+n*log(n/e))/log()+;

        printf("%lld\n",(ll)res);

    }

    return ;

}

巴特西

斯特林(Stirling)公式求大数阶乘的位数

最新文章

热门文章

巴特西

斯特林(Stirling)公式 求大数阶乘的位数

最新文章

热门文章

斯特林(Stirling)公式求大数阶乘的位数