奇怪的函数

题目描述 使得 xx 达到或超过 n 位数字的最小正整数x是多少？(n∈[1,2∗109])

题目链接 louguP2759 codevs3538 codevs1696 其实这个题目主要是推公式（数学水平要求：高一必修一） 不妨设n为 xk 的位数 即 xk=10n−1 （e.g 11=101−1 ，所以为是n-1） ∴ logxk=n−1 ∴ klogx+1=n

于是在这道题中就是求得一个 x∈[1,2∗109] 使得 xlogx+1=n 然后这个 x 似乎具备单调性

证明: 若llogl 1>n 那么比 l 的大的数x都满足 xlogx+1>n 同理 若 rlogr+1<n 那么比 r 的小的数x都满足 xlogx+1<n x <script type="math/tex" id="MathJax-Element-20">x</script>具备单调性得证

于是我们就可以二分答案了 于是就看代码吧

#include<cstdio> #include<cmath> int n,tl=1,tr=2e9,tm=(1+2e9)/2; int main(){ scanf("%d",&n); for(;tl<tr;(floor(tm*log10(tm))+1)<n?tl=tm+1:tr=tm,tm=(tl+tr)>>1);//奇葩的二分 return!printf("%d",tl); }