Digits of Factorial LightOJ

题目就不再发了，大致意思就是给你一个十进制数n，算出阶乘后转换成K进制的数，你来算一下它的位数。

坑点在哪呢，就是这个数可能算阶乘的时候没放弄了，比如1000000，做过最多单算阶乘的题也就是让你算到10000，所以这个如果按正常步骤来写肯定不行啦。

本题主要运用两个定理：

1丶十进制位数就是（int）log10（n），比如，1234，就是4，55555位数就是5。

对应K进制位数就是logk（n），但是math.h或者库函数里边log函数的底数只有固定的几个能直接用的，所以需要用到换底公式啦

2丶：loga（n）=logm（n）/logm（a）=ln（n）/ln（a）；

3丶：核心思想要求K进制位数：logk（n！）=ln（n！）/lnk + 1={ln（1）+ln（2）+ln（3）+...+ln（n）}/lnk + 1；

AC代码如下：大家看的时候可以自己再理解理解看看有没有更好的方法来解这道题啦，我这水平也有限，代码可能还不够完善呢。

#include<stdio.h>

#include<math.h>

#include<string.h>

#define ll long long

double aa[];

int main()

{   int t,c,m,n,i;

double ww;

scanf("%d",&t);

memset(aa,,sizeof(aa));

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

    aa[i]+=aa[i-]+log(i);//打个表来存一下前1000000个数的log（阶乘），会节省很多时间的

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

    {

        scanf("%d%d",&m,&n);

        if(m==)

            printf("Case %d: 1\n",i);

        else

           {

               ww=aa[m];//此处两行就是上边我介绍的核心思想了

            ww=ww/log(n)+;//至于为什么+1，自己再想想啦

            printf("Case %d: %d\n",i,(int)ww);

           }

    }

    return ;

}

巴特西

Digits of Factorial LightOJ - 1045

最新文章

热门文章