ACM 斯特林公式 Factorial vs Power

约定不等于承诺〃 2022-06-12 12:48 193阅读 0赞

斯特林公式（Stirling's approximation）是一条用来取n的阶乘的近似值的数学公式。一般来说，当n很大的时候，n阶乘的计算量十分大，所以斯特林公式十分好用，而且，即使在n很小的时候，斯特林公式的取值已经十分准确。

![20170723165334141][]

![20170723165504492][]

**SPOJ Factorial vs Power**

![20170723165054739][]

题目大意：对于给定的a，求满足的 n! > an 最小的n。

思路：利用斯特林公式，可以代替到n！的计算，就不会超范围也不会超时啦~~~

#include <iostream>
    #include <math.h>
    using namespace std;
    double PI=acos(-1.0);  
    bool check(long long n ,double a )  
    {  
        double x = (double )n;  
        double sum =  x * log(x) - x  + 0.5*(log(PI * 2 * x));  
        if(sum > x * log(a))  
            return 1;  
        else return 0;  
    }  
    int main()  
    {  
        int T;  
        cin>>T;  
        while(T--)  
        {  
            double  a ;  
            cin>>a ;  
            long long l = 1 , r=10*a;  
            long long mid  ;  
            while(l < r)  
            {  
                mid = (l  + r ) / 2;  
                if(check(mid,a))   
                r = mid ;    
                else  
                l = mid + 1;   
            }  
            cout<<l<<endl;  
        }  
    }

[20170723165334141]: /images/20220612/f9a4bdc612474e2e833cc3c62a2e258c.png
[20170723165504492]: /images/20220612/22562a95f47546a6b1c27930c1f7a9aa.png
[20170723165054739]: /images/20220612/6af5d9d18b324bd38d02dab980db6ea4.png

发表评论取消回复

表情：

评论列表（有 0 条评论，193人围观）

还没有评论，来说两句吧...

相关阅读

相关高等数学积分关系定理（格林公式、高斯公式、斯托克斯公式）的理解

1 格林公式、高斯公式、斯托克斯公式 1.1 格林公式（Green formula） ![在这里插入图片描述][77cd6a3a76044890a03d6f3c82

女爷i/ 2024年02月17日 12:32/ 0 赞/ 56 阅读

相关斯特林数 HDU 3625

/ 斯特林数第一类 n个元素的集合分成k个环排列的方法 s[n][0] = 0; s[1][1] = 1; s[n][

短命女/ 2022年09月29日 04:24/ 0 赞/ 163 阅读

相关求N!的位数（斯特林公式）

斯特林公式 lnN!=NlnN-N+0.5\ln(2\N\pi) 要想求有多少位，将他换成以10为底便可！利用换底公式得 lnN!/ln10=log10N!

拼搏现实的明天。/ 2022年08月04日 09:15/ 0 赞/ 214 阅读

相关 ACM 斯特林公式 Factorial vs Power

斯特林公式（Stirling's approximation）是一条用来取n的阶乘的近似值的数学公式。一般来说，当n很大的时候，n阶乘的计算量十分大，所以斯特林公式十分好用，而

约定不等于承诺〃/ 2022年06月12日 12:48/ 0 赞/ 194 阅读

相关【组合数学】第二类斯特林数

一、定义第二类Stirling数即:![SouthEast][]，又可记为![SouthEast 1][]\[与第一类的表示有大小写的区别\]。其表示将n个不同的元素分成

雨点打透心脏的1/2处/ 2022年06月01日 04:57/ 0 赞/ 562 阅读

相关牛顿-柯特斯公式

理论积分区间\[a,b\] \[ a , b \] ，划分为n等份。步长为 h=b−an h = b − a n 等距节点：xk=a\+kh

╰+攻爆jí腚メ/ 2022年05月20日 06:12/ 0 赞/ 296 阅读

相关斯特林公式 ——Stirling公式（取N阶乘近似值）

转载：[点我][Link 1] 版权声明：(代码仓库)\[https://github.com/LzyRapx\] https://blog.csdn.net/liangzh

朱雀/ 2022年05月15日 04:22/ 0 赞/ 466 阅读

相关求N的阶乘长度（斯特林公式）

输入N求N的阶乘的10进制表示的长度。例如6! = 720，长度为3。 [求N的阶乘长度][N] 计算n!的公式是斯特林公式: ![在这里插入图片描述][20190603

秒速五厘米/ 2022年01月23日 12:39/ 0 赞/ 264 阅读

相关 51Nod1130斯特林近似

![1575943-20190227195117036-288323810.jpg][] log10(n!)=log10(2\pi\n)\0.5+n\log10(n/e)

Dear 丶/ 2022年01月10日 06:43/ 0 赞/ 217 阅读

相关 POJ 1423 斯特林

题意：进制问题分析：打表，但是要用不能 long long 型，超内存。 n! = log\_\{10\}\\sqrt\{2\{\\pi\}n\}\(\\f

素颜马尾好姑娘i/ 2021年09月30日 11:44/ 0 赞/ 334 阅读