法一：对一个数求它的对数，+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
poj1423---求一个大数的位数方法，我猜网站上统计输入字符少于多少位的那个算法
原文：http://www.cnblogs.com/gabygoole/p/4471397.html