朴素公式为: log10(n!)=log10(1*2*3…*n)=log10(1)+log10(2)+…+log10(n) 求位数:log10(n!)=log10(1*2*3…*n)=log10(1)+log10(2)+…+log10(n),对log10(n!)的值取整加1就是n!的位数。 《计算机程序设计艺术》中给出了另一个公式 n! = sqrt(2*π*n) * ((n/e)^n) * (1 + 1/(12*n) + 1/(288*n*n) + O(1/n^3)) π = acos(-1) e = exp(1) 两边对10取对数 忽略log10(1 + 1/(12*n) + 1/(288*n*n) + O(1/n^3)) ≈ log10(1) = 0 得到公式 log10(n!) = log10(sqrt(2 * pi * n)) + n * log10(n / e) #include<iostream> #include<cmath> using namespace std; int main() { double Pi = acos(-1.0); double E = exp(1.0); int n,m; int len; cin >> m; while(m--) { cin >> n; len = (int)(log10(sqrt(2 * Pi * n)) + n * log10(n/E) + 1); if(n == 1) len = 1; cout << len << endl; } return 0; }
|
|