M_sea

洛谷2759 奇怪的函数
Luogu算法分析一下$x^x$。容易导出,$f(x)=x^x$的导函数为$f'(x)=x^x\cdot(\ln ...
扫描右侧二维码阅读全文
06
2018/12

洛谷2759 奇怪的函数

Luogu

算法

分析一下$x^x$。

容易导出,$f(x)=x^x$的导函数为$f'(x)=x^x\cdot(\ln x+1)$。

所以$x=\frac{1}{e}$时,函数取极值。

然后就可以知道当$x>\frac{1}{e}$时,函数单调递增。

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

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

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

其实以上全是废话

代码

#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;
}
最后修改:2019 年 05 月 26 日 03 : 25 PM

2 条评论

  1. smy

    这题为什么要求导

    不是直接用对数函数做吗

    1. M_sea
      @smy

      好玩而已

发表评论 取消回复