自动搬运

查看原文

来自洛谷，原作者为

	Mychael AFO

搬运于2025-08-24 21:41:16，当前版本为作者最后更新于2017-09-13 18:00:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

介绍求数x位数的方法：

x的位数=log10(x)+1;【取整】

log10(double)是cmath头文件里自带的10为底的对数

可是题目的数很大呐。

利用对数运算，可以把指数提出来，作为系数

即log(x^x)=x*log(x)

直接枚举x?试试看输入2000000000，发现过了10s才出答案两亿多

说明答案是整型范围内的，但时间效率却是O(200000000)太大了

考虑到10为底的对数函数是单调递增的，所以可以用二分答案

就成了O(log200000000)了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define LL long long int
using namespace std;
int main(){
    int n;
    LL L=1,R=2e9;
    cin>>n;
    while(L<R){
        LL mid=(L+R)>>1,len=(LL)(mid*log10(1.0*mid))+1;
        if(len<n) L=mid+1;
        else R=mid;
    }
    cout<<L<<endl;
    return 0;
}