专栏首页数据结构与算法洛谷P2759 奇怪的函数(log 二分)

洛谷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 条评论
登录 后参与评论

相关文章

  • 26:统计满足条件的4位数个数

    26:统计满足条件的4位数个数 总时间限制: 1000ms 内存限制: 65536kB描述 给定若干个四位数,求出其中满足以下条件的数的个数:  个位数上的...

    attack
  • 牛客NOIP提高组R1 A中位数(二分)

    设$s[i]$表示$1-i$中有多少比它大的,要求的长度为$len$,我们记下$s[i - len]$的最小值为$Mi$

    attack
  • 3673: 可持久化并查集 by zky

    Description n个集合 m个操作 操作: 1 a b 合并a,b所在集合 2 k 回到第k次操作之后的状态(查询算作操作) 3 a b 询问a,b是...

    attack
  • 26:统计满足条件的4位数个数

    26:统计满足条件的4位数个数 总时间限制: 1000ms 内存限制: 65536kB描述 给定若干个四位数,求出其中满足以下条件的数的个数:  个位数上的...

    attack
  • 2017广东工业大学程序设计竞赛初赛 题解&源码(A,水 B,数学 C,二分 D,枚举 E,dp F,思维题 G,字符串处理 H,枚举)

    Problem A: An easy problem Description     Peter Manson owned a small house in a...

    Angel_Kitty
  • 【未完成】【PAT520 钻石争霸赛】7-7 阶乘的非零尾数 (20分)

    “求 N 阶乘末尾的第一个非零数字”是一道常见的企业笔试题。这里我们略微做个变化,求 N 阶乘末尾的第一个非零 K 位数,同时输出末尾有多少个零。

    韩旭051
  • data_structure_and_algorithm -- 如何找到字符串中最长回文子串: python & java实现

    Given a string s, find the longest palindromic substring in s. You may assume th...

    MachineLP
  • Javascript是个好东西(广大人民的智慧是无穷的):

    图片发自简书App 1,面向对象? 其他编程语言对于面向对象要么支持,要么不支持,而js支持原型链,具体的实现要自己动手,实现的方式也是各种流派(相当于别人家的...

    zhaoolee
  • 分布式 | ddl 失败在 dble 中排查过程

    爱可生 dble 项目测试组成员,负责 dble 相关测试工作,拥有多年数据库中间件测试经验,擅长故障排查及性能调优。

    爱可生开源社区
  • 用ARM实现音乐电子相册

    Zoctopus

扫码关注云+社区

领取腾讯云代金券