[51nod1058]求N!的长度

法1：stirling公式近似

$n! \approx \sqrt {2\pi n} {(\frac{n}{e})^n}$

（如果怕n不够大下式不成立，可以当数小于10000时用for求阶层）

也可以用log10函数，不过直接使用log，e没有误差，一定注意longlong；

复杂度$O(1)$

 #include<bits/stdc++.h>

 #define PI  acos(-1.0)

 using namespace std;

 typedef long long ll;

 int main(){

     int n,t;

     cin>>t;

     double ans;

     while(t--){

         cin>>n;

         ans=(0.5*log(*PI*n)+n*log(n)-n)/log();

         cout<<(ll)ans+<<endl;

     }

     return ;

 }

法二：

直接for+log10循环求，复杂度$O(n)$

 #include<bits/stdc++.h>

 #define PI  acos(-1.0)

 using namespace std;

 typedef long long ll;

 int main(){

     int n;

     cin>>n;

     double ans=1.0;//对10取对数之后需要+1

     for(int i=;i<=n;i++){

         ans+=log10(i);

     }

     cout<<(int)ans<<endl;

     return ;

 }

巴特西

[51nod1058]求N!的长度

最新文章

热门文章