HDU 1018(阶乘位数数学)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意是求 n 的阶乘的位数。

直接求 n 的阶乘再求其位数是不行的，开始时思路很扯淡，想直接用一个数组存每个数阶乘的位数，用变量 tmp 去存 n 与 n - 1 的阶乘的最高位的数的乘积，那么 n 的阶乘的位数就等于 n - 1 的阶乘的位数加 tmp 的位数再减去 1。

但这种做法是不对的，例如有可能最高位与 n 的乘积结果是 99，而其实 n 与其他位的乘积结果是能进到这一位的，也就是说实际应该在 n - 1 的阶乘位数上增加 2 ( 3 -1 ) 位。而在对样例测试时也发现 n 为 10 的时候结果尚正确，但当 n 为 20 的时候就比正确结果少了 1，也就是说发生了上述情况。

抱着侥幸心理，又再次将每次乘以最高位的做法调整成了每次乘以最高的两位，这一次当 n 为 20 时结果依然正确，但是内存超了......

错误代码：

 #include <bits/stdc++.h>

 using namespace std;

 int tmp,dig[];

 int getdigit(int n)

 {

     int a();

     while(n)

     {

         n/=;

         a++;

     }

     return a;

 }

 void make()

 {

     int digit;

     dig[] = ;

     dig[] = ;

     dig[] = ;

     dig[] = ;

     tmp = ;

     for(int i = ; i <= ; i++)

     {

         tmp *= i;

         digit = getdigit(tmp);

         dig[i] = digit + dig[i-] - ;

         for(int j = ; j < digit; j++) tmp/=;

     }

 }

 int main()

 {

     int t,ans,n;

     scanf("%d",&t);

     make();

     while(t--)

     {

         scanf("%d",&n);

         printf("%d\n",dig[n]);

     }

     return ;

 }

在借鉴了其他人的做法后，才觉得对这道题有了一点正确的思路：

首先，一个数 x 的位数可以用以 10 为底取对数再向上取整的方法求得，即 digit( x ) = ceil ( log10( x ) )；

那么，阶乘的位数可以直接求：digit( n! ) = ∑ log10( i ) （ i 从 1 取到 n ）

代码如下：

 #include <bits/stdc++.h>

 using namespace std;

 int main()

 {

     int t,n;

     double ans;

     scanf("%d",&t);

     while(t--)

     {

         ans = ;

         scanf("%d",&n);

         for(int i = ; i <= n; i++)

         {

             ans += log10(i);

         }

         printf("%d\n",(int)ans+);

     }

     return ;

 }

另外，在求 n 的阶乘的时候用 Stirling 公式也是很好的做法，

代码如下：

 #include <bits/stdc++.h>

 using namespace std;

 const double pi = acos(-);

 int main()

 {

     int t,n,ans;

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d",&n);

         ans = ceil((log(n)*n - n + 0.5*log(*pi*n) )/ log());

         printf("%d\n",ans);

     }

     return ;

 }