hdu-1018-Big Number

发布时间:2016-12-11 20:13:03 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu-1018-Big Number",主要涉及到hdu-1018-Big Number方面的内容,对于hdu-1018-Big Number感兴趣的同学可以参考一下。

//此法不行,超时 #include<stdio.h> #include<string.h> #define M 60000000 int a[M]; int main() {  int s;  scanf("%d",&s);  while(s--)  {   int n,i,j,m,c,t;   scanf("%d",&n);   memset(a,0,sizeof(a));   a[0]=1;   m=0;   for(i=2;i<=n;i++)   {    c=0;    for(j=0;j<=m;j++)    {     t=a[j]*i+c;     a[j]=t%10;     c=t/10;     if(j==m&&c!=0)      m++;    }   }   printf("%d\n",m+1);  }  return 0; }   这题要求n的阶乘的位数,如果n较大时,n的阶乘必将是一个很大的数,题中说1<=n<10000000,当n=10000000时可以说n的阶乘将是一个非常巨大的数字,对于处理大数的问题,我们一般用字符串,这题当n取最大值时,就是一千万个数字相乘的积,太大了,就算保存在字符串中都有一点困难,而且一千万个数字相乘是会涉及到大数的乘法,大数的乘法是比较耗时的,就算计算出结果一般也会超时。这让我们不得不抛弃这种直接的方法。再想一下,这题是要求n的阶乘的位数,而n的阶乘是n个数的乘积,那么要是我们能把这个问题分解就好了。在这之前,我们必须要知道一个知识,任意一个正整数a的位数等于(int)log10(a) + 1;为什么呢?下面给大家推导一下:  对于任意一个给定的正整数a,  假设10^(x-1)<=a<10^x,那么显然a的位数为x位,  又因为  log10(10^(x-1))<=log10(a)<(log10(10^x))  即x-1<=log10(a)<x  则(int)log10(a)=x-1,  即(int)log10(a)+1=x  即a的位数是(int)log10(a)+1我们知道了一个正整数a的位数等于(int)log10(a) + 1,现在来求n的阶乘的位数:假设A=n!=1*2*3*......*n,那么我们要求的就是(int)log10(A)+1,而:log10(A)        =log10(1*2*3*......n)  (根据log10(a*b) = log10(a) + log10(b)有)         =log10(1)+log10(2)+log10(3)+......+log10(n)现在我们终于找到方法,问题解决了,我们将求n的阶乘的位数分解成了求n个数对10取对数的和,并且对于其中任意一个数,都在正常的数字范围之类。总结一下:n的阶乘的位数等于  (int)(log10(1)+log10(2)+log10(3)+......+log10(n)) + 1 总结后的代码: #include<stdio.h> #include<math.h> int main() {  int s;  scanf("%d",&s);  while(s--)  {   int n,i;   double t;   scanf("%d",&n);   t=0.0;   for(i=1;i<=n;i++)    t+=log10(i);   printf("%d\n",(int)t+1);  }  return 0; }      

上一篇:《经济半小时》 20130906 指尖上的商机(五)数据时代
下一篇:插入排序(直接插入排序、希尔排序)

相关文章

相关评论