法一:对一个数求它的对数,+1取整为其位数
问题转化为int (log10(N!)+1),对数性质log10(N!)=log10(N)+log10(N-1)+...+log10(1)
/*用log10求位数*/ #include<stdio.h>
#include<math.h> int main()
{
int tim,N;
scanf("%d",&tim);
while(tim--)
{
int i;
double NumOfDigit=1;
scanf("%d",&N);
for(i=N;i>=1;i--)
{
NumOfDigit+=log10(i);
}
printf("%d\n",(int)NumOfDigit);
}
}
当n偏大的时候,时间长,TLE
法二:Stirling公式
log(n!) = log10(sqrt(2*pi*n)) + n*log10(n/e);
/*用斯特灵求位数*/ #include<stdio.h>
#include<math.h>
#define e 2.718281828459045
#define pi 3.141592653589793239
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&N);
double num_digit;
num_digit=log10(sqrt(2*pi*N)) + N*log10(N/e);
printf("%d\n",(int)num_digit+1);
}
return 0;
}
WA两次原因:
num_digit=log10(sqrt(2*pi*N)) + N*log10(N/e)+1;
printf("%d\n",(int)num_digit);
当N=1,num_digit=0.几,因为当n=1时,
log10(sqrt(2*pi*N)) + N*log10(N/e)=-0.03
最后值就为0
总结:用斯特林公式求位数时,考虑到N=1,加1放在取了整之后
(int)(log10(sqrt(2*pi*N)) + N*log10(N/e))=0
加1放在取了整之后 int(3.1+1)=4
int(3.1)+1=4
int(3)+1=4
int(3+1)=4
int(-0.03)+1=1
int(-0.03+1)=0