c++ 二分答案

问题

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

分析

对与这种较难求解的问题，我们很难想出较好的解决策略。但是，我们至少知道答案一定在1与2000000000之间，能否转换二分查找的思想，对答案进行二分查找呢？当然是可以的，但在二分查找中有比较，在二分答案中，我们也需要有比较，我们用检查函数来实现。如果检查出的是一个合法的解，那么我们尝试找更优的解，如果检查出的是不合法的解，我们尝试找合法的解，这就是二分答案的思想。在这题中，我们设计的检查函数就是x^x的数位是否超过n位，合法返回真，不合法返回假。再二分求解即可。

AC代码

#include <bits/stdc++.h>
using namespace std;
int o;
bool check(int k)//查看这个数的位数 
{
    long long p = k;
    return p * log10(1.0*k) + 1 >= o;//判断数位的公式 
}
int medium()
{
    int l = 0;//确保范围在 l 和 r 之间  
    int r = 2000000000;
    while (l + 1 < r)//确保不越界(l < r) 
    {
        int mid = (l + r) / 2;
        if (check(mid))//如果这个解满足要求 
        {
            r = mid;//缩小范围 
        }
        else//如果这个解不满足要求 
        {
            l = mid;//继续在右半部分寻找解  
        }
    }
    if (check(l))//如果解合法 
    {
        return l;
    }
    else//不合法 
    {
        return r;
    }
}
int main()
{
    cin >> o;
    cout << medium() << endl;
    return 0;
}

备注:
公式推导:

版权声明：本文为LJA001162原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/LJA001162/p/11184517.html