[牛客OI测试赛2]F假的数学游戏(斯特灵公式)
2018-09-10 00:58:29来源:博客园 阅读 ()
题意
输入一个整数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 */
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 捕获未经测试的返回值 2020-04-11
- 设计并测试Trapezium类 代码参考 2020-03-29
- 测试博客 2019-10-25
- 牛客网中矩阵中的路径 2019-10-25
- 测试 2019-09-30
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash