BZOJ3000 Big Number

题意：求n!在b进制下的位数（n<=2^31）。

好像要高精！？好像会TLE！？根本不会做！

然后想到answer=∑log(k,i)

然后积分？∫ln(x) dx = xln(x) - x

小数据直接跑，过之。试个极限数据，差了3！？

仔细一想，对数函数是凹的，这样算答案当然会偏小。

百度了一下，发现有个公式：n!≈√(2*π*n)*(n/e)^n。

拆开之后发现就是比原来的积分多了个ln(2*π*n)

#include <cstdio>

#include <cmath>

const double pi = asin(1) * 2.0;

double calc(double n, double k) {

double ans = 0;

if (n < 100000) {

for (int i = 1; i <= n; ++ i)

ans += log(i);

ans /= log(k);

}

else {

ans = (0.5 * log(pi * n * 2) + log(n) * n - n) / log(k);

}

return ans + 0.5;

}

int main() {

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

#endif

double n, k;

while (scanf("%lf%lf", &n, &k) != EOF)

printf("%.0lf\n", calc(n, k));

}

积分……跪烂
底下那个斯特林公式说真的小数据差的太远（如果20应该叫做小数据）

Comments