M_sea

洛谷2759 奇怪的函数
题目描述使得$x^x$达到或超过$n$位数字的最小正整数$x$是多少?传送门算法分析一下$x^x$。它的定义域是$...
扫描右侧二维码阅读全文
18
2018/07

洛谷2759 奇怪的函数

题目描述

使得$x^x$达到或超过$n$位数字的最小正整数$x$是多少?

传送门

算法

分析一下$x^x$。

它的定义域是$(0,+\infty)$。
虽然不容易求导它的单调性,但是容易知道在区间$[1,+\infty)$上它是单调递增的。
也就是说,对于任何$x\in{N^{+}}$,当$x$增加时,$x^x$也增加。

那么直接二分$x$即可。

但是$x^x$的位数怎么求呢?

易得:$a$的位数为$[lg\ a+1]$。
那么$x^x$的位数为$[lg\ {x^x}+1]$。
又因为$log_a\ n^m=m\ log_a\ n$,
所以$x^x$的位数为$[x\ lg\ x+1]$。

完结。

代码

#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline bool check(int x,int n) {
    if (x*log10(x)+1>=n) return 1;
    else return 0;
}

mainint main() {
    int n; scanf("%lld",&n);
    re int L=1,R=2100000000;
    while (L<R) {
        re int mid=(L+R)>>1;
        if (check(mid,n)) R=mid;
        else L=mid+1;
    }
    printf("%lld\n",L);
    return 0;
}
最后修改:2018 年 11 月 09 日 04 : 47 PM

发表评论