poj1423---求一个大数的位数方法，我猜网站上统计输入字符少于多少位的那个算法

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

法一：对一个数求它的对数，+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;
}