牛客OI赛制测试赛2 F题非打表题解

## UPD 我太菜了..忘记了一个叫斯特林公式的东西..其实就是把我推的那个换成 $blnb-b+\frac{lnb}{2}+ln(\frac{\pi}{2})$ 当时试着同时调整 $0.5$ 和 $1$ 两个参数，还注意到了当数据范围变大时调大时 $lnb$ 的系数变大会更优，竟然没想到 $lnb$ 的系数就是 $0.5$ ...然后当时调的常数也在 $0.92$ 附近..以后要眼熟一下 $ln\pi\approx1.837877$ ------------ [题目地址](https://www.nowcoder.com/acm/contest/185/F) 比赛的时候用python打的表，直接算没有取对数，然后就打了50分的表...其实当时有想过对数，但脑抽了没发现取对数优化非常大。 因为给 $x$ 求 $n$ 非常诡异，下文中均为给 $a$ 求 $b$ 题目所求即最小的 $b$ 满足 $ln(b!)>ln(a^a)$ $ln(a^a)=a*ln(a)$ 不用多说.. $ln(b!)=\sum\limits_{i=1}^bln(i)$，直接求可以快速的打表，然而写到程序中算会TLE. 考虑到这题精度要求不高，试着找到一种求 $ln(b!)$ 近似值的方法。由 $\sum\limits_{i=1}^bln(i)$ 想到可以积分，也就是 $\int_1^bln(x)dx=bln(b)-b+1$，这个求出来是 $ln(b!)$ 的近似下界. 然而直接这样求会WA几个点，考虑将下界继续逼近。  如图即为少算的部分，可以近似看作一堆底为 $1$，高的和为 $ln(b)$ 的三角形，面积和就是 $\frac{ln(b)}{2}$。 可以看出 $bln(b)-b+1+\frac{ln(b)}{2}$ 是 $ln(b!)$ 非常接近的上界，二分求解是可以AC的，然而对拍了一下发现还是很容易卡我的... 代码： ``` #include <iostream> #include <cstdio> #include <cmath> using namespace std; int main() { long long x; cin>>x; long long l=x,r=x*2,mid; while (l<r) { mid=(l+r)/2; if (log(mid*1.0)*mid-mid+0.5*log(mid)+0.9<x*log(x)) { l=mid+1; } else { r=mid; } } cout<<l; return 0; } ``` [在线函数图像](https://www.desmos.com/calculator/4h1fe86qit) $ln(x!)\ $ **vs** $\ xln(x)-x+1+\frac{ln(x)}{2}$