斯特林公式求阶乘位数
题目只需看红字部分!!
1129: 第五章:一不小心爱上你
Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 574 Solved: 147
[Submit][Status][Web Board]Description
O型血的人大多数是行动派,郑微更是将这个特征发挥到了极致。次日上课,阮阮前所未有地发现她在课堂上奋笔疾书,大为惊讶,便凑过去问了一声,“在写什么呀?”郑微大大方方地向阮阮展示了她一早上的智慧结晶,阮阮看了看,“俘虏陈孝正详细行动攻略……”她念完,顿时无语。挺漂亮的一本崭新小本本,上面已经洋洋洒洒地写了将近十页,蝇头小字,字字工整,各个环节、各个步骤无一不详,关键地方和注意事项甚至还用下划线标了出来。
行动攻略第一条:在自习教室偶遇陈孝正,郑薇坐在了他的后面,假装不知道,问了他一个数学问题:你知道520的阶乘有多少位么?但是,陈孝正却根本没有理睬郑薇。。
这个问题的答案,你知道么?赶紧想好了,如果哪天有人来问你。。。。。。
Input
每行一个N,0<=N<10^7,你要快速回答哦!
Output
输出N的阶乘的位数。
Sample Input
5 6 520
Sample Output
3 3 1189
HINT
他在这些传言里每天照常晨练,照常上课,照常自习,照常生活,照常独来独往,从不刻意躲闪别人的眼神,也不刻意澄清,只是淡漠地,仿佛他们说着的是别人的故事,只不过在远远看到郑微时,掉头的脚步更快了。但郑微并不害怕他的回避,一个学校能有多大,有心找一个人总能找到,何况是他这样生活规律的家伙。郑微没有真正经历过爱情,她不知道别人的爱情是怎么样的,她只有凭着自己的直觉,倾尽所能地去靠近她爱的那个男孩。
法一:
用log10(i)计算,但是这道题的maxn很大,会TLE
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <map>
#include <list>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#define go(i,a,b) for(int i=a;i<=b;i++)
#define og(i,a,b) for(int i=a;i>=b;i--)
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn = 1e2 + 5;
typedef long long ll;
int main()
{
int n;
while(scanf("%d",&n) != EOF)
{
double sum = 0.0;
go(i,2,n) sum += log10(i);
int ans = (int)ceil(sum);
cout<<ans<<endl;
}
return 0;
}
法二:
用斯特林公式,参考博客链接
用了这个公式就能又快又好的算出阶乘的位数了,妈妈再也不怕我TLE了啦
【斯特林公式模板】
int digit_stirling(int n) { double PI=acos(double(-1));// PI的值=反余弦函数 -1.0为Pi, 1为0。 double e=exp(double(1));//e的值 return floor(log10(sqrt(2*PI*n))+n*log10(n/e))+1; }
【通过代码】
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <map>
#include <list>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#define go(i,a,b) for(int i=a;i<=b;i++)
#define og(i,a,b) for(int i=a;i>=b;i--)
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn = 1e7 + 5;
int digit_stirling(int n)
{
double PI=acos(double(-1));// PI的值=反余弦函数 -1.0为Pi, 1为0。
double e=exp(double(1));//e的值
return floor(log10(sqrt(2*PI*n))+n*log10(n/e))+1;
}
int main()
{
int n;
while(scanf("%d",&n) != EOF)
{
if(n == 1 || n == 0)
cout<<1<<endl;
else cout<<digit_stirling(n)<<endl;
}
return 0;
}