洛谷P2759 奇怪的函数(log 二分)

题目描述

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

输入输出格式

输入格式:

一个正整数 n

输出格式:

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

输入输出样例

输入样例#1: 复制

11

输出样例#1: 复制

10

说明

n<=2000000000

比较套路,首先转化一下题面,我们需要找到一个最小的$x$,使得

$x^x > 10^n$

两边同时取$log$

$xlog_{10}x > n - 1$

由于log函数有单调性,因此可以二分$x$

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
#include<iostream>
#define int long long  
using namespace std;
const int MAXN = 4 * 1e5 + 10, mod =  100003;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
main() {
    int l = 0, r = 1LL * 20000000001, ans = -1, N = read();
    if(N == 1) return !printf("1");
    while(l <= r) {
        int mid = l + r >> 1;
        if(mid * log(mid) / log(10) > N - 1) r = mid - 1, ans = mid;
        else l = mid + 1;
    }
    cout << ans;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏IT可乐

Java数据结构和算法(九)——高级排序

  春晚好看吗?不存在的!!!   在Java数据结构和算法(三)——冒泡、选择、插入排序算法中我们介绍了三种简单的排序算法,它们的时间复杂度大O表示法都是O(...

3926
来自专栏我是攻城师

Scala中的case match语法

2613
来自专栏数据结构与算法

2189 数字三角形W

2189 数字三角形W 时间限制: 1 s 空间限制: 32000 KB 题目等级 : 黄金 Gold 题目描述 Description 数字三角...

2557
来自专栏编程坑太多

Python 字典

1094
来自专栏用户2442861的专栏

Python之逻辑运算和缩进和选择if

作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢!

681
来自专栏梧雨北辰的开发录

Swift学习:泛型

本篇将详细总结介绍Swift泛型的用法; Swift泛型代码让你能够根据自定义的需求,编写出适用于任意类型、灵活可重用的函数及类型。它能让你避免代码的重复,用...

872
来自专栏数据结构与算法

P2513 [HAOI2009]逆序对数列

题目描述 对于一个数列{ai},如果有i<j且ai>aj,那么我们称ai与aj为一对逆序对数。若对于任意一个由1~n自然数组成的数列,可以很容易求出有多少个逆序...

2838
来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》第3章 Python的数据结构、函数和文件3.1 数据结构和序列3.2 函数3.3 文件和操作系统3.4 结论

本章讨论Python的内置功能,这些功能本书会用到很多。虽然扩展库,比如pandas和Numpy,使处理大数据集很方便,但它们是和Python的内置数据处理工具...

4656
来自专栏数据结构与算法

1081 线段树练习 2 单点查询及区间修改

1081 线段树练习 2 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 大师 Master 题目描述 Description ...

3189
来自专栏技术小站

c++(二)

算数运算符:+,-,*,/,%,++,--  进行算数运算时,如果存在溢出,则把溢出的部分拿掉(浮点型的难以预测),如 int i=0xffffffff,j;j...

1051

扫码关注云+社区

领取腾讯云代金券