最近做了杭电上的一个题hdu1018，就是求一个数的阶乘有多少位数。比如10！= 3628800，有7位数。所以，当输入10的时候就输出7。开始以为很简单，看了一下数据范围n <= 10e7就懵逼了。傻傻地在那里找规律，无果，只好狼狈的百度了。
** 先看下题： **
在百度途中get到了一个新知识，我们都知道由
1og10（N） = X可以转换成10eX = N，那么就可以得到N的位数就为X+1，因为10有两位数，所以要加1。（10e2 = 100，3位数）。也就是说，(int)(log10(N)) + 1就是N的位数。
又因为n! = n(n - 1)(n - 2)......3 * 2 * 1，设n!的位数为k，则k = (int)(log10(n!)) + 1 = (int)(log10(n) + log10(n - 1) + log10(n - 2) +......+ log10(3) + log10(2) + log10(1)) + 1;
2秒10的7次方可以过。所以可以得到如下暴力代码：
#include <iostream>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <queue>
#include <map>
#include <stack>
#include <utility>
#include <algorithm>
using namespace std;
#define PI 3.14159265
#define e 2.71828182
typedef pair<double, double> P;
const int MAX_N = 1 << 17;
int main() {
//ios::sync_with_stdio(false);
//cin.tie(NULL);
//cout.tie(NULL);
int t;
scanf("%d", &t);
while (t--) {
double n;
scanf("%lf", &n);
double ans = 1;
for (double i = 1; i <= n; ++i) {
ans += log10(i);//log10()是math中的函数，直接用
}
printf("%d\n", (int)ans);
}
return 0;
}
当然，重点在这里，更简单的办法：
同时对两边取对数：
log10(n!) = log10(sqrt(2 * PI * n)) + n * log10(n / e);所以k = (int)(log10(sqrt(2.0 * PI * n)) + n * log10(n / e)) + 1;很容易写出代码：
#include <iostream>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <queue>
#include <map>
#include <stack>
#include <utility>
#include <algorithm>
using namespace std;
#define PI 3.14159265
#define e 2.71828182
typedef pair<double, double> P;
const int MAX_N = 1 << 17;
int main() {
//ios::sync_with_stdio(false);
//cin.tie(NULL);
//cout.tie(NULL);
int t;
scanf("%d", &t);
while (t--) {
double n;
scanf("%lf", &n);
double res = log10(sqrt(2.0 * PI * n)) + n * log10(n / e);
int ans = (int)(res) + 1;
printf("%d\n", ans);
}
return 0;
}
关于斯特林的证明，百度上说的很详细了，这里就不累赘了。(__) 嘻嘻……
