[牛客OI测试赛2]F假的数学游戏(斯特灵公式)
程序员文章站
2022-07-02 21:02:03
题意 输入一个整数X,求一个整数N,使得N!恰好大于$X^X$。 Sol 考试的时候只会$O(n)$求$N!$的前缀和啊。 不过最后的结论挺好玩的 $n! \approx \sqrt{2 \pi n} (\frac{n}{e})^n$ 然后就可以$O(1)$算啦 ......
题意
输入一个整数x,求一个整数n,使得n!恰好大于$x^x$。
sol
考试的时候只会$o(n)$求$n!$的前缀和啊。
不过最后的结论挺好玩的
$n! \approx \sqrt{2 \pi n} (\frac{n}{e})^n$
然后就可以$o(1)$算啦
/* */ #include<iostream> #include<cstdio> #include<cstring> #include<set> #include<algorithm> #include<map> #include<cmath> #define pair pair<int, int> #define fi first #define se second #define mp(x, y) make_pair(x, y) #define ll long long const ll maxn = 1e8 + 10, mod = 100000007, inv = 50000004; using namespace std; inline ll read() { char c = getchar(); ll x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } const double pi = acos(-1), e = exp(1.0); ll n, x; double up; bool check(double n) { return 0.5 * log(2 * pi * n) + n * log(n / e) >= up; } int main() { x = read(); /*if(x == 7) {printf("10"); return 0;} if(x == 77) {printf("94"); return 0;} if(x == 777) {printf("892"); return 0;} if(x == 7777) {printf("8640"); return 0;} if(x == 77777) {printf("84657"); return 0;} if(x == 777777) {printf("834966"); return 0;} if(x == 7777777) {printf("8267019"); return 0;} if(x == 77777777) {printf("82052137"); return 0;} if(x == 777777777) {printf("815725636"); return 0;} if(x == 7777777777ll) {printf("8092563686"); return 0;}*/ up = x * log(x); // for(ll i = 1; i <= 1e8; i++) lg[i] = log(i), s[i] = s[i - 1] + lg[i]; //cout << lg[10]; int times = 51; double l = 1, r = 1e13, ans; while(times--) { ll mid = (l + r) / 2; if(check(mid)) ans = mid, r = mid; else l = mid; } cout << (long long)ans; return 0; } /* 2 4 6 4 6 */
上一篇: 研究显示安保机器人目前还无法阻止偷窃行为
下一篇: NOIP2000 提高组 T3 单词接龙