洛谷P2759 奇怪的函数
? 解题记录 ? ? 洛谷 ? ? 数学 ? ? 二分答案 ?    2017-11-05 12:50:30    649    0    0

题目描述

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

输入输出格式

输入格式:

 

一个正整数 n

 

输出格式:

 

使得 x^x 达到 n 位数字的最小正整数 x

 

输入输出样例

输入样例#1: 复制
11
输出样例#1: 复制
10

说明

n<=2000000000

对于任意的X,其实x^x的位数是可以通过公式计算的:log10(x) * x + 1(可以问问百度 )。这样我们可以很容易的验证答案。于是很容易就想到了二分答案。所以我们二分X的值就可以了,代码如下:

#include<iostream>
#include<algorithm>
#include<cmath>
#define LL long long
using namespace std;
LL n;
LL ct(LL x) {
    return (LL)floor((log10(x)) * (long double)x) + 1;
}

LL DF(LL l, LL r) {
    while(l < r) {
        int mid = l + r >> 1;
        if(ct(mid) < n) l = mid + 1;
        else r = mid;
    }
    return l;
}

int main() {
    cin >> n;
    cout << DF(0, 1 << 30);
    return 0;
}

上一篇: 洛谷P3275 [SCOI2011]糖果

下一篇: 洛谷P2106 Sam数

649 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航