题解 P2759 【奇怪的函数】

panyf · 2019-07-23 10:46:41 · 题解

先上7行最短蓝题代码:

#include<bits/stdc++.h>
using namespace std;
int n,l=1,r=3e8,m;
int main(){
    for(cin>>n,n--;m=(l+r)/2,l<r;)if(m*log10(m)<n)l=m+1;else r=m;
    cout<<l;
}

求位数方法：

正整数m的位数为[lg(m)]+1([ ]表示向下取整,lg即为log10）

证明：

由于m为正整数，必然存在正整数n使得10^(n-1)<=m<10^n，则m的位数为n，对此不等式取对数得n-1<=lg(m)<n，故m的位数为[lg(m)]+1。

分析：

本题求x^x的位数，也就是求[lg(x^x)]+1，利用对数的运算法则，lg(x^x)=x* lg(x)，由于直接解出x的值较为困难，这里运用了二分的思想。

注释代码：

#include<bits/stdc++.h>
using namespace std;
int n,l=1,r=3e8,m;
/*l必须初始化为1，否则会RE，本题中n最大为2e9
   所以r最大为238723448，这里初始化为3e8*/
int main(){
    cin>>n,n--;
//所求位数为int(m*log10(m)+1，所以n先减1
    while(l<r){//二分
        m=(l+r)/2;
        if(m*log10(m)<n)l=m+1;
        else r=m;
    }
    cout<<l;
}