首页 > 代码库 > HDU 1018 Big Number (简单数学)
HDU 1018 Big Number (简单数学)
Big Number
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 25649 Accepted Submission(s): 11635
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
21020
Sample Output
719
Source
Asia 2002, Dhaka (Bengal)
Recommend
JGShining
这道题我一开始用的大数求阶乘的方法做的,结果超时,O(N2)的算法伤不起。
先挂一下超时的代码
1 #include<cstdio> 2 #include<cstring> 3 #include<stdlib.h> 4 #include<algorithm> 5 using namespace std; 6 int main() 7 { 8 int kase,num[3000],i,j; 9 scanf("%d",&kase);10 while(kase--)11 {12 int n;13 scanf("%d",&n);14 memset(num,0,sizeof(num));15 num[0]=1;16 for(int i=2;i<=n;i++)17 {18 int c=0;19 for(int j=0;j<3000;j++)20 {21 num[j]=num[j]*i+c;22 c=num[j]/10;23 num[j]=num[j]%10;24 }25 }26 for(i=2999;i>=0;i--)27 if(num[i])28 break;29 printf("%d\n",i+1);30 }31 return 0;32 }
后来一想,就算不超时,10^7的阶乘也存不下,所以一时之间没有思路。
后来上网看大神怎么做的,才AC了。
如果要计算一个数num的位数,那么可以用到 (int)lg((double)num)+1
这里lg(1*2*3......n)=lg1+lg2+lg3+......lg n
这里的话可以将1~10^7的数的位数全部存起来,是一种打表的做法。
1 #include<cstdio> 2 #include<cmath> 3 #include<cstring> 4 #include<stdlib.h> 5 using namespace std; 6 int a[10000005]; 7 int main() 8 { 9 a[1]=1;10 double sum=0;11 for(int i=2;i<=10000000;i++)12 {13 sum+=log10((double)i);14 a[i]=sum+1;15 }16 int kase,n;17 scanf("%d",&kase);18 while(kase--)19 {20 scanf("%d",&n);21 printf("%d\n",a[n]);22 }23 return 0;24 }
当然还有一种做法就是用到了斯特林数
公式为:
求出阶乘然后同样的方法取位数,求出lg(n!)再向上取整
1 #include<cstdio> 2 #include<cmath> 3 #include<cstring> 4 #include<stdlib.h> 5 const double PI=3.141592654; 6 const double e=2.718281828; 7 using namespace std; 8 int main() 9 {10 int kase,n;11 double sum;12 scanf("%d",&kase);13 while(kase--)14 {15 scanf("%d",&n);16 sum=log10(2*PI*n)/2+n*log10(n/e);17 printf("%d\n",(int)sum+1);18 }19 return 0;20 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。