P2759 奇怪的函数（二分答案，数学运算）

P2759 奇怪的函数

范围$2e9$2e9，直接枚举肯定超时，正着直接求答案求不出来，那么运用逆向思维，直接二分答案判断即可。这道题涉及简单的数学运算。

要$x^x>=n$xx>=n位数，而n位数$==10^{n-1}$==10n−1，所以问题转换为二分答案，查找x使得$x^x>=10^{n-1}$xx>=10n−1，两边取log，$log_{10}x^x>=n-1$log10​xx>=n−1
$xlog_{10}x>=n-1$xlog10​x>=n−1，按照这个条件直接调用log10函数判断二分即可。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cmath>
#include<vector>
#define ls (p<<1)
#define rs (p<<1|1)
//#define mid (l+r)/2
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A
const ll N=1e5+7;
const ll INF=1e10+9;
const ll mod=2147483647;
const double EPS=1e-10;//-10次方约等于趋近为0
const double Pi=3.1415926535897;
ll n,m,a[N];

int main()
{
    scanf("%lld",&n);
    ll l=1,r=2e9; 
    while(l<r)
    {
        ll mid=(l+r)/2;
        if(ll(mid*log10(mid)+1)<n)l=mid+1;
        else r=mid;
    }
    printf("%lld\n",l);
    return 0;
}