laekov

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));

}


评论(1)

© laekov | Powered by LOFTER