洛谷P2759 奇怪的函数(log 二分)
题目描述
使得 x^xxx 达到或超过 n 位数字的最小正整数 x 是多少？
输入输出格式
输入格式：
一个正整数 n
输出格式：
使得 x^xxx 达到 n 位数字的最小正整数 x
输入输出样例
输入样例#1： 复制
11输出样例#1： 复制
10说明
n<=2000000000
比较套路，首先转化一下题面，我们需要找到一个最小的$x$，使得
$x^x > 10^n$
两边同时取$log$
$xlog_{10}x > n - 1$
由于log函数有单调性，因此可以二分$x$
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
#include<iostream>
#define int long long
using namespace std;
const int MAXN = 4 * 1e5 + 10, mod = 100003;
inline int read() {
char c = getchar(); int 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;
}
main() {
int l = 0, r = 1LL * 20000000001, ans = -1, N = read();
if(N == 1) return !printf("1");
while(l <= r) {
int mid = l + r >> 1;
if(mid * log(mid) / log(10) > N - 1) r = mid - 1, ans = mid;
else l = mid + 1;
}
cout << ans;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-07-10 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录