hello kity
期待您的批阅,由于写解题报告时 不一定考虑的很周到,所以如果您有什么不懂的地方,请您留言,然而一天之内我肯定会看见您信息,再对代码注释详细,让您更好的阅读
分类
最新评论
最新留言
链接
RSS
计数器
222872
功能
HDU 1018(Big Number 求N!的位数,各种求法!)
spoiler
posted @ 2011年4月20日 20:34
in 斯特林数的各种应用
, 3481 阅读
题目:
Problem Description
In many applications very large integers numbers are required. Some of these applications are using keys for secure transmission of data, encryption, etc. In this problem you are given a number, you have to determine the number of digits in the factorial of the number.
|
Input
Input consists of several lines of integer numbers. The first line contains an integer n, which is the number of cases to be tested, followed by n lines, one integer 1 ≤ n ≤ 107 on each line.
|
Output
The output contains the number of digits in the factorial of the integers appearing in the input. |
Sample Input
2 10 20 |
Sample Output
7 19 |
题目分析:
第一种做法:
N!=1*2*3....*n
求位数我们一般用对一个数取对数就可以了 ,
log10(n!)=log10(1)+ log10(2) +log10(3)...+log10(n);
所以循环求和就可以了!
但是这里注意一点 结果要加1!因为这里计算出来的 log10(1)=0 !
所以结果要加上这个误差 ‘1’
第二种做法:
这就是我最近研究的斯特林数,第一类斯特林数就可以做这个!
补充一点,斯特林数能够做一切关于阶乘有关的大数运算 要深入学习!
这里给出递归公式:
log10(n!)=1.0/2*log10(2*pi*n)+n*log10(n/e)
然后我就附上代码了;
两种做法都有!
#include<iostream> #include<cmath> #include<cstdio> #define e 2.7182818284590452354 #define pi acos(-1) using namespace std; int main(){ int cas,ans,n; cin>>cas; while(cas--){ scanf("%d",&n); ans=(int)(1.0/2.0*log(2.0*pi*n)/log(10.0)+1.0*n*log(n/e)/log(10.0)+1); printf("%d\n",ans); } return 0; }
#include<iostream> #include<cmath> #include<cstdio> #define e 2.7182818284590452354 #define pi acos(-1) using namespace std; int main(){ int cas,ans,i,n; double sum; cin>>cas; while(cas--){ scanf("%d",&n); sum=1; for(i=1;i<=n;i++) sum+=log10(i); printf("%d\n",((int)sum)); } return 0; }
2011年4月20日 21:14
我首先想到的是把 N! 算出来然后转换成字符串然后求长度。。。。
2011年4月21日 01:21
@依云: 嘿嘿 以后就用这种方法吧 嘿嘿 很高兴能让您有所启发 呵呵
2011年4月21日 04:49
@hello kity: 还是算了吧,速度慢就算,还在 Ctrl-C 的时候导致 Python 出现段错误。。。
>>> len(str(factorial(10000000)))
^Czsh: segmentation fault python3
2011年4月21日 20:19
@依云: 您理解错了,我是说介绍您用这种算法。。。呵呵
2011年7月17日 19:45
请问那个公式是怎么推出来的?
PS:cmath里面自带log10()。这里就不用麻烦用换底公式了= =