Rockdu's Blog

题目描述

使得 x^x 达到或超过 n 位数字的最小正整数 x 是多少？

输入输出格式

输入格式：

一个正整数 n

输出格式：

使得 x^x 达到 n 位数字的最小正整数 x

输入输出样例

11

10

说明

n<=2000000000

对于任意的X，其实x^x的位数是可以通过公式计算的：log10(x) * x + 1（可以问问百度 ）。这样我们可以很容易的验证答案。于是很容易就想到了二分答案。所以我们二分X的值就可以了，代码如下：

#include<iostream>
#include<algorithm>
#include<cmath>
#define LL long long
using namespace std;
LL n;
LL ct(LL x) {
    return (LL)floor((log10(x)) * (long double)x) + 1;
}

LL DF(LL l, LL r) {
    while(l < r) {
        int mid = l + r >> 1;
        if(ct(mid) < n) l = mid + 1;
        else r = mid;
    }
    return l;
}

int main() {
    cin >> n;
    cout << DF(0, 1 << 30);
    return 0;
}