ACM 斯特林公式 Factorial vs Power

本文主要是介绍ACM 斯特林公式 Factorial vs Power，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

 SPOJ Factorial vs Power

题目大意：对于给定的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;  }  
}  

 

 

 

 

 

 

这篇关于ACM 斯特林公式 Factorial vs Power的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---