斯特林公式

定义：

斯特林公式是用来求N的阶乘近似值的公式：
公式为：
$n!=\sqrt{2\pi n}(\frac{n}{e})^n$

公式的应用：求n！的位数
大家都知道，求一个十进制数n的位数，可以对10取对数然后加一，即：
$l o g 10 (n) + 1$
假设ans代表n！的位数，则
$ans=log10(n!)+1=log10(\sqrt{2\pi n}(\frac{n}{e})^n)+1=log10(\sqrt{2\pi n})+log10(\frac{n}{e})^n+1---(1)$
或者：
$a n s = l o g 10 (n!) + 1 = l o g 10 (1) + l o g 10 (2) + . . . . . . + l o g 10 (n - 1) + l o g 10 (n) + 1 - - - (2)$

案例：

1.求N！的位数：

在这里插入图片描述
解题：直接运用斯特林公式(2)

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define ll long long
using namespace std;
int main(){
int m;cin>>m;double sum=0;for(int i=1;i<=m;i++){sum+=(double)log10(i);//以浮点数加 //c++支持log2(),ln()即log(),log10() }sum+=1;cout<<(int)sum<<endl;//sum向下取整 return 0;
}

2. N!的位数（n更大，n<=10^9）

解题：直接运用斯特林公式(1）

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define ll long long
using namespace std;
double pi=acos(-1.0);
double e=exp(1.0);
int main() {int t;cin>>t;while(t--) {ll n;cin>>n;ll len=log10(sqrt(2*pi*n))+n*log10(n/e)+1;cout<<len<<endl;}
}

3.求N的阶乘的准确值

在这里插入图片描述
解题：由于n最大到10000，即使用long long也无法表示，所以计算结果需要保存在数组中。

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define ll long long
using namespace std;
int main() {int ans[50000],n;//ans数组用于存储结果 int cnt=1,carry=0,res;//cnt表示计算结果位数，carry表示进位，res中间变量 while(cin>>n) {for(int i=0; i<50000; i++)ans[i]=0;//初始化赋0 ans[0]=1;for(int i=2; i<=n; i++) {for(int j=0; j<cnt; j++) {res=ans[j]*i+carry;//i与ans数组的每一位相乘 ans[j]=res%10;//存储个位数字 carry=res/10;}while(carry>0) {//处理最高位的进位 ans[cnt++]=carry%10;carry/=10;}}for(int i=cnt-1; i>=0; i--)cout<<ans[i];//从高到低位输出 cout<<endl;}return 0;
}

4.N的阶乘同余P

在这里插入图片描述
解题：每做一次乘法，将结果mod P

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define ll long long
using namespace std;
int main(){
ll N,P;
cin>>N>>P;
ll ans=1;
for(int i=1;i<=N;i++){
ans=ans*i%P;	
} 
cout<<ans<<endl;
return 0;
}