-数论-二分- [洛谷 P2759]奇怪的函数

题目描述

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

输入格式

一个正整数 $n$

输出格式

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

输入样例

11

输出样例

10

说明

n<=2000000000

Solution

直接暴力枚举当然不可取，不仅会TLE而且还会精度爆炸，所以我们要做一些优化

显而易见，$x^x$的位数是$\log{10}{x^x}$，也就是$n=\log{10}{x^x}$。

而且我们还知道$\log{a}{b^m}=m\log{a}{b}$；

所以$\log{10}{x^x}=x\log{10}{x}$。

因为n<=20000000000，所以我们要用二分。

Code

#include<iostream>
#include<cstdio>
#include<cmath>
#define MAX 100000000
#define lg(x) (x)*(log10((x)))//因为以10为底的对数都简写作lg，所以我就用lg表示了，而且使用define时千万不要吝惜括号！！(重要)
using namespace std;
int main() {
    long long n,p,m,l=1,h=20*MAX;
    scanf("%lld",&n);
    while(l<=h) {
        m=(l+h)/2;
        if(n<=(lg(m)+1)) {
            p=m;
            h=m-1;
        } else {
            l=m+1;
        }
    }
    cout<<p<<endl;
    return 0;
}