luogu p2759 奇怪的函数Solution

奇怪的函数 问题描述     使得x^x达到或超过n位数字的最小正整数x是多少？ 输入数据     输入一个正整数n。 输出数据     输出使得x^x达到n位数字的最小正整数x。 输入样例 11 输出样例 10 时间限制     各测试点1秒 内存限制     你的程序将被分配32MB的运行空间 数据规模     n<=2 000 000 000 这里是题面_(:зゝ∠)_ 看到这道题一开始的感觉当然是暴力枚举啦，但是我瞟了一眼数据范围，我*****； 猴，然后下面是正解， 首先，对于数字2*10^9，o(n)肯定是过不去的，那么我们考虑一下o(logn), 于是我们便想到了二分查找，完美； void merge(ll l,ll r){ if(l==r){ printf("%lld",l); return; } ll m=(l+r)/2; if(cac(m)>=n)merge(l,m); else merge(m+1,r); } 其中cac（m）是指m^m的位数，那么问题来了，m^m的位数又怎么求呢 _(:зゝ∠)_ (╯‵□′)╯︵┻━┻这是最烦的了； 于是我经过仔(qiu)细(zhu)思(du)考(niang) 找到了一个神奇的东西，没错就是麦森数w； 公式：     n=向下取整(t*log2(t))+1; 猴，那么现在问题就解决了吧_(:зゝ∠)_  于是我们得到cac()的函数体： ll cac(ll t){ if(t==1)return 1; return floor((log(t)/log(10))*t)+1; }  然后这道题是不是很简单qwq，我还是太弱了 代码贴上w： #include<cstdio> #include<cmath> #define maxn 2000000000 #define ll long long using namespace std; ll n; template <class T> inline void read(T&a){\\读入优化     char c=getchar();     bool flag=0;     if(c=='-')flag=1;     for(a=0;c<'0'||c>'9';c=getchar());     for(;c>='0'&&c<='9';c=getchar())(a*=10)+=c-'0';     if(flag)a=-a; } ll cac(ll t){ if(t==1)return 1; return floor((log(t)/log(10))*t)+1; }  void merge(ll l,ll r){ if(l==r){ printf("%lld",l); return; } ll m=(l+r)/2; if(cac(m)>=n)merge(l,m); else merge(m+1,r); } main(){ read(n); merge(1,maxn); return 0; }